dp
-
[PS] 백준 2293번: 동전 1, 2294번: 동전 2카테고리 없음 2023. 11. 30. 22:26
동전 1 동전 2 dp연습하며 고른 문제이다. 무엇을 기준으로 dp를 할까 엄청 고민하다 결국 힌트를 봐버렸다. 총 가격으로 dp를 한다는 아이디어를 얻자마자 쉽게 풀 수 있었다. dp는 언제쯤 익숙해질까... 이런식으로 n원을 내기 위한 총 경우의 수를 계산하면 된다. 동전2는 저기서 경우의수가 대신 n원당 내야하는 동전의 수로 업데이트 하도록 바꿔 쉽게 연계해서 풀었다. // 동전 1 #include using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i < static_cast(N); i++) #define FORL(e, S) for (auto& e : S) int n, k; vector coins; int dp[1000..