백준 2294번 동전 2 풀이/해설/코드 (파이썬) 다이나믹 프로그래밍을 활용해보자

코드만 궁금한 분은 깃허브링크

 

사실 내가 dp를 잘 하는 편은 아닌데 2293번 어제 푼거를 머릿속에 생각해보면서 푸니까 그래도 다소 어렵지 않게 풀 수 있었다.

 

문제를 대충 알려주자면, 1, 2, 5 이런식으로 무작위의 숫자들과 다른 숫자 임의의 숫자 하나가(예시를 들기 위해 10으로 한다.) 주어진다. 이 때 앞쪽에 주어진 숫자 1, 2, 5들을 이용해 10을 구성하는데 그 때 가장 적은 수로 숫자들을 이용하는 경우를 반환하면 된다. 말이 좀 이상한데, 간단히 얘기해서 10은 1을 10번 써도 되지만 5를 2번 써도 된다. 그럼 2가 더 작으니까 답은 2가 된다.

 

문제 풀기

 

1. 구성해야 하는 숫자 N의 길이만큼의 리스트를 미리 만든다.

2. 앞에 무작위로 주어졌던 숫자들 중 작은 수부터 활용해서, 1부터 N까지의 숫자들을 만들 때 사용해야 하는 갯수의 최솟값을 업데이트한다.

3. 가장 큰 수까지 해서 N까지 다 업데이트 한 다음 그 때의.. 값을 반환하면 된다.

 

말이 이상하니까 예시를 들어서 다시 설명하자면

 

1. 1을 사용해서 1을 만들 때에는 숫자가 1개 필요하다.

2. 1을 사용해서 2를 만들 때에는 (1을 만들때의 갯수 +1 )개 만큼 필요하다. = 2

3. 1을 사용해서 3을 만들 때에는 (2를 만들때의 갯수 +1 )개 만큼 필요하다. = 3

.

.

4. 1을 사용해서 9를 만들 때에는 8을 만들때의 갯수 +1개를 해서, 9개만큼의 수가 필요하다.

5. 그런데 1과 5를 사용해서 9를 만들 때에는 두가지 경우가 나오게 된다.

  - 1만을 사용해서 8을 만들때의 갯수 + 1 = 9.

  - 1만을 사용해서 4를 만들고 거기에 5를 한개 추가해서 9를 만들때의 갯수 = 4 + 1.

두개를 비교하면 당연히 아래쪽이 더 수가 작기때문에 1,5만을 이용해서 9를 구성하게 되면 그 때 필요한 숫자의 최소 갯수는 총 5개이다. 

 

이런 식으로 더 큰숫자가 추가될 때마다 최솟값을 업데이트하는 식으로 하면 문제를 풀 수 있다. 설명을 잘 하려고 노력했는데 이해가 안되면 코드를 봐주세요..!!