그리디 기출 문제 04 만들 수 없는 금액

문제를 봐도 도저히 효율적으로 풀 방법이 떠오르지 않아 결국 비효율적으로 해결했다. 

 

문제는 답안을 살펴봐도 알고리즘이 동작할 것이라는 건 확인할 수 있었지만, 왜 어떻게 동작할 수 있는지에 대해 파악하는 것이 어려웠다. 

 

관련하여 나와 동일한 고민을 하고 내용을 정리해놓은 글을 아래 링크로 걸고, 글을 읽으며 든 생각을 정리한다. 

 

https://kk-programming.tistory.com/11

[이코테-그리디] 기출 - 04. 만들 수 없는 금액

동전 [1, 2, 3, 5, 13] 일 때 문제를 해결해보자.

 

아래는 target 을 1로 초기화하고, coin의 단위에 따라 업데이트하는 과정이다. 

코드 구현 

target = 1 
for x in coin:
    if target < x:
        break 
    target += x

 

해당 문제의 골자는 다음과 같다.

 

업데이트한 target 은 target 이하의 값들은 모두 생성할 수 있다는 것을 보장한다. 

그리고 target 을 업데이트 하기 위해서는 업데이트한 target 의 값이 다음 처리할 동전의 단위보다 같거나 커야한다. 

target >= x: 
	pass

실제 코드는 아래와 같지만, 결국 위의 코드를 의미한다. 

target < x:
	break

 

즉, 다음 동전의 단위가 기존 만들 수 있다고 확인 된 값에 그전 단위 동전을 더한 것보다 작거나 같으면 업데이트하는 target 까지 만들 수 있다고 보장하게 되는 것이다. 

 

우리가 구하고자 하는 것은 만들 수 없는 금액의 최소 단위이다. 

다음 동전 단위가 "기존 만들 수 있는 것" + 그전 단위 동전인데, 그것보다 크다면 조건을 만족 할 수 없다. 그 중에서도 가장 최적의 조건일 때 아래와 같이 된다. 

 

다음 동전 단위: 50 

기존 만들 수 있는 것 + 그전 단위 동전: 49 ( - 처음 추가된 1) = 48 

48, 50 사이의 49를 만들 수 없게 된다. 

 

즉 다음 동전 단위는 "기존 만들 수 있는 것" + 그전 단위 동전 >= 다음 동전 단위 이어야 한다. 

가장 hard 조건인 "기존 만들 수 있는 것" + 그전 단위 동전 == 다음 동전 단위 는 

다음 동전 단위 49 

기존 만들 수 있는 것 + 그전 단위 동전: 49 (- 처음 추가된 1) = 48 

48 만들고, 49 이므로 가능하다. 

 

여기서 바로 이어나가서 다음 target 을 97로만들어도 

1 ~ 48 조합 + 49  이므로 97까지 모두 가능한 것이 우선 확인 되고 

97 보다만 x 가 같거나 작으면 그 사이값은 다 채워져 있기 때문에 문제가 없다는 것을 확인할 수 있다. 

 

코드도 워낙 단순하고 직접 적어보면 알고리즘이 동작한다는 것을 확인 할 수 있지만, 그 구조를 직관적으로 이해한다는 것이 참 어려운 문제였다. 그리디보다는 논리 구조가 DP 에 가까운 문제가 아니었나 싶다.