[백준 / #2294 / C++] 동전 2

한동안 여행을 다녀와서 문제를 풀지 못해 업로드 하지 못했다..

 

이번 문제는 다이나믹 프로그래밍 연습 겸 해서 풀어봤다. 상당히 쉬운 문제였다.

 

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

2294번: 동전 2

 

문제 해석:

 

 

이번 문제는 동전 1과 비슷한 문제이지만 최소로 사용되는 동전의 수를 구하면 되는 문제이다. 최소로 동전을 사용하여 어

 

떤 값을 만들려면 최솟값에 최솟값을 더하여 만들면 자연스레 최솟값이 될 것이다. 이러한 관점에서 보면 다이나믹 프로그

 

래밍(Dyanamic Programming, 이하 DP)로 풀면 금방 풀릴 것이다. 자료의 최대 크기는 10,000과 100으로 두 개를 곱하여

 

도 1,000,000으로 충분히 주어진 시간인 1초 이내에 나올 것이다.

 

 

알고리즘 해설 및 코드:

 

 

 

점화식은 매우 간단하다. 각각의 값에서 주어진 동전의 가치를 각각 하나씩 빼보며 만약 현재의 값에서 동전의 값을 뺀 dp

 

값에 + 1 한 값이 현재 값의 dp 값보다 작을 경우 현재 값의 dp 값을 교체해준다. 그렇지 않을 경우 그대로 둔다. 이 때, 한가

 

지 예외를 처리해주어야 하는데 동전의 값에 해당하는 dp 값을 계산할 때는 무조건 동전 1개로 나타낼 수 있기 때문에 이러

 

한 경우에만 dp 값을 1로 설정해준다. 이 이후의 연산은 모두 동일하다. 그렇게 모든 dp 값을 채워나가면 되는 것이다.

 

 

 

굉장히 빠른 시간 내에 풀린 문제라 뭔가 문제 티어 배치가 잘못된건 아닌가 생각했지만 DP 문제가 한 번 안보이면 잘 안보

 

이므로 어려울 수도 있겠다는 생각이 드는 문제였다.