문제 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 풀이 DP문제이다. i번째 coins를 쓰는 경우, 안쓰는 경우를 비교한다. i번째 coins을 쓰면 dp[j-coins[i]] + 1이 점화식이다. 5원을 써서 11원 만드는 방법을 고안한다 하면, dp[11]과 dp[11-5] + 1을 비교한다. 어렵다.......................... dp어케하냐 코드 n,k = map(int,input()...

조건 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모이제이션(Memoization) 다이나믹 프로그래밍을 구현하는 방법 중 한 종류 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져옴 캐싱이라고도 함. 한 번 구한 정도를 리스트에 저장하는 방식으로 사용 → 사전 자료형 사용할 수 있음. 탑다운(하향식): 재귀 함수를 이용, 큰 문제 해결하기 위해 작은 문제 호출 피보나치 수열 #한번 계산된 결과 메모이제이션 하기 위한 리스트 초기화 d = [0] * 100 #피보나치 함수를 재귀함수로 구현(탑다운) def fibo(x): #종료 조건 if x==1 or x==2: return 1 #이미 계산한 ..