3. 동전1 다이나믹 프로그래밍 문제 (Baek-Joon 사이트 2293번)

1. 문제

출처: https://www.acmicpc.net/problem/2293

2. 출력

2-1) 코드

2-2) 출력

2-3) 결과

3. 해설

 정말 오래 헤맸다. 정말 단순한 건데 지금까지 리커젼 방식으로 풀려다가 메모리 제한에 걸려서 헤맸다. 

그리고 이 문제를 풀면서 배운 것. 

(1) 다이나믹 프로그래밍은 결국 반복문으로 변환 가능해야 함. (내가 착각하던 것 너무 리커젼과 메모 조합으로 풀려함)

(2) 점화식은 모든 경우를 고려한 점화식이어야 함. (결국 모든 경우를 찾는 것, 메모 방식이 횟수를 줄일 뿐)

리커젼 >> 반복

반복 >> 리커젼

으로 각각의 변환 과정을 이해하자.