동적계획법. [2293]

[1. 문제 설명]

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

---

[2. 풀이 접근]

재귀와 메모이제이션을 통한 구현

그러나 문제 조건 상, 메모리 제한이 4MB 이므로,

메모이제이션 및 재귀 호출을 위한 공간복잡도를 만족하지 못한다.

 

이 경우 고려해야 하는 것이, 반복적 동적계획법

• 부분 문제간의 의존성을 파악하기 쉬울 경우에는 반복문을 이용하여 동적계획법을 구현 할 수 있다.
• 반복적 동적계획법은 계산되는 순서를 고민해야 하기 때문이다.
• 슬라이딩 윈도 기법을 통한 공간복잡도를 줄일 수 있다.
• 재귀적 동적계획법과 마찬가지로 구현 패턴을 정리한다.
  => 기저사례 작성
  => 계산 순서를 고려한 반복문 작성

 

이번 문제에서 부분 문제간 의존성을 정리하면 아래와 같다.

• m 원이 되도록 동전을 선택하는 경우는
• (m - coin[i]) 이 되도록 동전을 선택하는 경우의 수를 더하면 된다.
  => i 번째 코인을 선택한 경우를 의미함.
• 동전을 선택하는 순서는 고려하지 않는다.
• ex) coin 순서가 3, 1, 2, 5, 6, 7
  => m==5, coin[i] = 3 인 경우, 2 원을 만드는 경우의 수를 누적한다.
  => 2원을 만드는 경우가 (1+1) 혹은 (2) 인 경우, 이렇게 두가지가 존재
  => 그러나, coin[i]==1, coin[i]==2 인 경우를 아직 확인하지 않았다,
  => coin[i] == 5 인 차례에서, 2원을 만드는 경우를 확인하는 경우가 생긴다.
  => 이때 누적되는 것 같다.
• cache[i] 에 누적되는 것이 현재가 정확하지 않더라도, 나중에 다시 더하는 경우가 생긴다.

---

[3. 코드]