[리뷰] 그리디 - 만들 수 없는 금액

github.com/ndb796/python-for-coding-test

ndb796/python-for-coding-test

문제는 늘 그렇듯 책을 사서 보시길...

일단 정답 코드는 매우 간결하다. 하지만 그 코드를 짜기까지의 아이디어가 생각보다 어렵다.

여기서의 로직은 n-1까지의 모든 수를 만들 수 있다는 가정하에 n번째 수를 만들 수 있는가? 라는 질문을 계속 하는 것이다. 무슨 말인지는 전혀 모를 수 있다. 하나하나 파해쳐보자.

 

우선 입력 받은 동전들을 오름차순으로 정렬하고 싶은 욕구는 매우 클 것이다(^^). 그리고 동전들을 하나씩 꺼내고 싶을 것이다. 

 

그런다음 1원부터 주어진 동전들로 만들 수 있는지 확인할 것이다.

처음으로 꺼내는 동전이 1원이면 만들 수 있다. 2원이상이면 만들 수 없는 최소 금액은 1원이다.

 

그런다음 2원를 만들 수 있는지 확인해야한다. 여기서 1원은 당연히 만들 수 있다

여기서 다음으로 꺼내는 동전이 1원 동전이 이면 2원을 만들 수 있다. 당연한 말이지만 꺼내는 동전이 2원이며 2원을 만들 수 있다.  하지만 3원 이상의 동전들 밖에 없으면 2원을 만들 수 없다.

 

그럼 정렬된 동전 배열이 [1, 2, ...]이라고 하면

1원 2원 동전들이 있으니까 3원이 있는지 굳이 확인할 필요가 없다. 바로 4원을 만들 수 있는지 확인해야한다.

마찬가지로 1원 2원 3원 4원 동전들이 있다면 4원을 만들 수 있다. 하지만 5원 이상의 동전들이 있으면 만들 수 없는 최소 금액은 4원이다.

 

예를 하나 더 들고 싶지만 이 이후는 각자 생각해보자...

 

결론적으로 "n-1원을 만들 수 있다는 가정하에 n원을 만들 수 있습니까?"라는 질문은 꺼내는 동전-k원이 n원 이하이면 n원을 만들 수 있다. 그리고 다음으로 꺼내는 동전에게는 n+k원을 만들 수 있습니까?라는 질문을 던지는 것이 적절하다.

 

그래서 결과 코드는 다음과 같다.

 

파이썬

import sys

n = int(input())
arr = list(map(int,sys.stdin.readline().rstrip().split()))
arr.sort()
possible = 1
for elem in arr:
  if possible >= elem:
    possible += elem
  else:
    break
print(possible)

 

c++

#include <bits/stdc++.h>

using namespace std;

int main() {
  
  int n;
  vector<int> v;
  cin>>n;
  int possible = 1;

  for(int i = 0; i < n; i++){
    int tmp;
    cin>> tmp;
    v.push_back(tmp);
  }

  sort(v.begin(),v.end());

  for(int i = 0; i < n; i++){
    if(possible >= v[i]){
      possible += v[i];
    }  
    else break;
  }
  cout<<possible<<'\n';
}