[Week of DP] BOJ 2294 #2

내가 접근했던 방식은

각 동전들이 몇 개를 가지면 될지 조합해보는 거였다.

 

문제의 예제를 기준으로

6은 1원짜리 1개랑 5원짜리 1개로 구성되어 있으니까

1원짜리 몇 개와 5원짜리 몇 개가 필요한지 구하면 될 거라고 생각했다.

 

그.러.나.

인터넷에서 찾아본 결과

이게 정상적인 풀이구나..라는 생각이 들 정도로

완전 다른 식으로, 그리고 매우 간편하게 해결한 풀이를 찾았다. (jaemin8852.tistory.com/163)

 

일단 DP라는 배열(Python에서는 리스트)을 선언하고

1원을 가지고 만들 수 있는 최소 개수를 구해준다.

그 후에 5원, 12원으로 만들 수 있는 최소 갯수를 구해주는 식이다.

 

여기서 유의해야 할 것은

DP[0]은 0으로 초기화해야 하며

그 외 나머지 DP 배열의 값은 최댓값으로 설정해주어야 한다.

 

또한 최소 개수는 목표로 하는 DP의 값과, DP[목표로 하는 값 - 동전의 가격] + 1이 된다.

예를 들어,

목표로 하는 값이 15이면(동전의 가격은 8)

MIN(DP[15], DP[15 - 8] + 1)이다.

 

상기의 설명은 매애애애애우 간단해 보이나

이런 방법을 생각해내는 건 매우 어려운 과정인 것 같다.

어찌 보면 답을 찾는 방법 중에 하나니까

문제에 따라 비슷하게 풀 수 있는 파훼법을 찾은 걸 수도 있다.

 

이 문제와 비슷한 문제의 조건(AND 조건)

- 각 요소들이 개수를 갖고 있으며

- 최솟값이나 최댓값을 구하는 문제

 

다음번 문제는 이번에 풀었던 경험을 바탕으로

인터넷 검색 없이 풀 수 있었으면 좋겠다!