728x90 메모리 제한 썸네일형 리스트형 [백준알고리즘] 2293번: 동전 1 -C [백준알고리즘] 2293번: 동전 1 -C https://www.acmicpc.net/problem/2293 단계별로 풀어보기 마지막 '동적 계획법 1'의 마지막 문제였다. 그래서 기쁜 마음으로 봤는데 생각보다 쉬워서 흡족했다..ㅎㅎ 처음에는 일단 가볍게 동전 가치의 내림차순으로 정렬한 후에 재귀를 사용해서 해봤다. 역시나 시간초과가 발생했다. 그래서 다음에 사용한건 nsize와 target의 크기를 입력받아 nsize x target행렬을 만든 것이다. 이때부터는 점화식을 사용했기 때문에 내림차순 정렬이 필요없어진다. 사용했던 점화식은 다음과 같다. dp[i][j] = dp[i - 1][j] + dp[i][j - nlist[i]] (i번째 동전없이 j가치를 만들 수 있는 방법의 수) + (i번째 동전을.. 더보기 이전 1 다음