백준 2293. 동전 1

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

2293번: 동전 1

 

프로그래머스의 거스름돈 문제 (https://tose33.tistory.com/520)와 똑같은 문제였다.

이 문제는 최대 메모리 제한이 4MB로 역시 거스름돈 문제때와 같이 다차원 배열로 풀면 정답을 받을수 없는 문제였다.

거스름돈 문제와 같이 동전이 1,2,5 동전이라면 

동전 1으로 만드는 경우,

동전 1,2로 만드는 경우 

동전 1,2,5로 만드는 경우를 나눠서 생각해야 했다.

 

5원을 만드는 경우를 생각해보면 

5원을 1원으로 만드는 경우는 11111 한 가지 이다.

5원을 1,2원으로 만드는 경우는 5-2 = 3원에서 2원을 추가하면 되기 때문에 3원을 1원으로 만드는 경우 + 3원을 1,2원으로 만드는 경우를 더한 값이다.

 

또한 다차원 배열로 풀수는 없으므로 1차원 배열에 저장해야 하기 때문에 

1원 동전으로 1 ~ k원을 만드는 경우를 모두 구하고 

1,2원 동전으로 만드는 경우를 더하고 

1,2,5원 동전으로 만드는 경우를 더하는 식으로 하면 1차원 배열로 풀수있다.