[BOJ][DP] 2293. 동전 1

문제 -> https://www.acmicpc.net/board/view/10754

금방 풀릴 것 같은 예감과 함께

즐겁게 생각을 했으나..

역시나. 오래걸렸다..

결국 풀이를 참고할 수밖에 없었고..

DP를 이제 나름 꽤 푼 것같은데 실력이 안느는것일까...

각설하고.

1 ~ 10원까지 세 가지 동전을 조합하여 

나오는 경우의 수를 DP 배열에 넣고,

그 DP를 이용하여 계속 10원까지 계산한다는 식의 접근 방법을

많이 떠올렸을 것이라 생각한다. (내가 이랬다)

위의 경우 중복을 고려하여 일일이 다 빼줘야하는데,

그럴경우 재귀로 구현해야한다. 

쉽게 코드 몇줄로 이 문제를 풀 수가 있는데,

사용자가 입력한 값들중에서

제일 작은 값을 최대한 활용하여 나머지 입력 값들에 대한

경우의 수를 구해줘야 한다. 

문제에 있는 예제를 보고 이해를 해보자.

1, 2, 5만을 이용하여 10을 만들어야 한다.

1원만 사용하여 위의 가격을 만들 때, 당연히 죄다 경우의 수는 한개밖에 나오지 않는다.

2원을 추가로 사용하여 위의 가격을 만든다고 할 때,

이런 표가 완성 될 것이다.

설명을 덧 붙이자면,

아까 미리 구해뒀던 1의 경우의 수를 활용한다고 했다.

이제 규칙을 찾는 것이다.

Mn[j]를 n의 동전을 포함하여 j가격을 만들 수 있는 경우의 수라고 할때,

M2[i] = M1[i] + M2[i-2]라는 규칙이 보인다.

이 말은 즉, 현재 동전을 추가한다고 할 때, 추가하기 전 금액의 경우의수를 

구해서 더해준다는 말. 

(예를 들어 M2[4]를 구하려면 M2[2]와 M1[4]를 더하면 된다는 것)

위를 구현하면 2차원 배열을 사용하게 되는데, 문제에서 주어진 메모리 크기는 4MB다.

2차원 배열을 쓰기엔 크기가 적어서 1차원 배열로만 해결을 해야한다. 

그렇다면,  그냥 현재 구하고 있는 동전값을 빼준 인덱스를 가지고 있는 dp값을 계속 더해주기만 하면 된다.

소스