[C++] 2294번 동전 2

다이나믹 프로그래밍 문제.

분명 동전 1을 풀었었는데, 풀이가 잘 생각이 나지 않아서 예전에 블로그에 썼던 글을 살짝 보고 풀었다.

문제가 비슷하긴 한데 동전 1은 경우의 수의 개수를 묻는 문제라면

이 문제는 어떤 경우의수가 나오는지를 묻는 문제였다.

물론 동전 1의 풀이를 안다면 쉽게 풀 수 있었을 것 같다.

 

처음에 동전의 가치가 100,000보다 작거나 같은 자연수

라는 조건을 읽지 못해서 틀렸었다.

이 말의 뜻은, 동전의 가치가 원하는 값보다 클 수 있다는 것을 의미한다.

 

문제풀이

n가지 동전이 있을때, 각 동전을 몇 가지를 사용하는지를 나누어서 계산하면 된다.

테스트 케이스를 예시로 들자면,

 

1만 사용했을 때

1	2	3	4	5	6	7	...
1개	2개	3개	4개	5개	6개	7개

 

1, 5를 사용했을 때

1	2	3	4	5	6	7	...
1개	2개	3개	4개	1개	2개	3개

빨간색으로 색칠한 부분이 바뀐 것을 알 수 있다.

동전 1과 마찬가지로

새로 추가된 동전의 값에 해당하는 수부터 업데이트 시켜주면 된다.

 

1, 5, 12를 사용했을 때

11	12	13	14	15	16	17	...
3개	1개	2개	3개	3개	2개	3개

12가 추가됐으므로, 12부터 업데이트 시켜준다.

이 때, 파란색 15가 중요하다.

15원은 동전 5 x 3으로 나타낼 수 있다. 이게 최소로 사용하는 경우이다.

그렇다면 어떻게 고려할 수 있을까?

동전의 가지수를 i개를 사용한다 하고, 현재 추가된 동전의 값을 add라고 하고, 각 동전의 가지수마다 값 j의 최소 경우의 수를 저장하는 2차원 배열을 dp배열이라 하고 min(A, B)는 A, B의 최소값을 반환한다고 한다면

• dp[i][j] = min(dp[i - 1][j], dp[i][j - add] + 1)

이라고 할 수 있다.

이 가정은 물론 추가된 동전의 값 add 이전까지의 경우의 수(dp[i][1] ~ dp[i][add - 1])까지는 dp[i - 1][1] ~ dp[i - 1][add -1]과 똑같이 초기화가 돼 있다는 가정이 있다.

 

왜 저렇게 나타낼 수 있을까?

1. dp[i - 1][j] : 탐색하는 값 j에 대해 동전의 종류를 하나 또는 더 적게 사용했을 때 동전을 적게 사용했다는 것을 의미한다. j가 그 이전의 추가된 동전들의 배수일 때를 고려해 주는 것이다.
2. dp[i][j - add] + 1 : 탐색하는 값 j가 추가된 동전의 값을 빼고 남은 값이 이전에 탐색됐었는지를 체크한다. 후에 추가된 동전의 개수 1개만 추가해주면 된다. j의 동전의 수 = (j - add)를 나타내는데 필요한 동전의 수 + 1(add, 추가된 동전의 수) 이다.

 

코드를 살펴보자.

 

사용한 STL과 변수

동전의 개수 coinCnt와 찾고싶은 값 wantSum을 변수로 만들어준다.

그리고 각 동전의 값을 입력받는 coin 배열,

[사용하는 동전의 개수][값]으로 몇 개의 동전을 최소로 쓰는지 저장하는 dp배열,

결과로 찾고싶은 값을 쓰려면 최소 몇 개의 동전이 필요한지 저장하는 result값이 있다.

result 값은 찾았다면 무조건 초기화할 수 있게 100001의 값으로 초기화했다.

 

메인함수 - 1

처음에 동전의 개수와 찾고싶은 값을 입력받는다.

 

그리고 dp배열의 모든 원소들을 100001으로 초기화시켜준다.

이는 최초로 찾은 동전의 개수로 무조건 초기화시켜줄 수 있도록 설정한 것이다.

만일 100001의 값을 가졌다면 해당 값은 표현하지 못한다는 것을 의미한다.

 

그리고 각 동전을 입력받은 후에

맨 처음 입력받은 동전을 사용했을 때의 나타낼 수 있는 값들을 모두 초기화시켜준다.

 

메인함수 - 2

for 반복문을 돌면서 사용하는 동전의 개수를 하나씩 늘린다.

각 반복문마다 추가된 동전의 값을 addCoin이라는 변수에 넣어놓는다.

 

그리고 현재 추가된 동전 이전의 값들중 탐색된 값들은 그 이전 동전 가지수에서 가져와야하므로 초기화시켜준다.

 

후에 반복문을 한번 더 돌면서 위에서 고려한 점화식을 바탕으로 dp배열에 값을 넣어준다.

만일 현재 탐색하는 j값이 내가 찾고자 하는 값이었다면 result값을 갱신해준다.

 

만일 result가 100001이라면, 나타낼 수 없다는 뜻이므로 -1을,

아니라면 result값을 출력해준다.

 

처음에 런타임 에러는 위에서 말했다시피, 동전의 가치가 찾고자 하는 값보다 큰 경우가 있어서 틀렸다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인이 가능하다.