목록배낭 문제 (1)

1일1알

백준 9084번 동전 C++

dp로 해결할 수 있는 문제이다. 배낭 채우기 문제와 비슷하다. dp[n+1][m+1]배열을 만들었다. dp[i][j]의 의미는 i번 동전까지 사용해서 j원을 만들 수 있는 경우의 수 라고 정하였다. 동전 몇개로든 0원은 언제나 만들 수 있어서 dp[i][0]은 모두 1로 초기화 해주었다. i번째 동전까지 사용해서 j원을 만들 수 있는 경우는 1) i-1번째 동전까지 사용하고 j원을 만든 상태에서 아무 행동도 하지 않는 경우와 2) i번째 동전까지 사용했는데 j-coins[i]원을 만든 상태에서 coins[i]를 추가해서 j원을 만드는 경우가 있다. 따라서 점화식은 dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]] 로 세우고 문제를 해결하였다. #include #include #..
알고리즘 2022. 3. 15. 11:52
이전 Prev 1 Next 다음