[이것이 코딩테스트다] 실전 - 만들 수 없는 금액*

나의코드

# 나의코드
# 조합
from itertools import combinations

n = int(input())
t=[]
array = list(map(int, input().split()))
# 주어진 수로 만들 수 있는 모든 조합 만들기
for i in range(2,n+1):
    t+=list(combinations(array,i))
# 각 조합의 합구하기
s = list(map(sum,t))
s += array
# 중복된 숫자를 제거하여 주어진 수들로 만들 수 있는 모든 정수가 담긴 리스트
s = list(set(s))

# 가장 작은 수가 1이 아니라면 1 반환
if s[0]>1:
    print(1)

else:
    for i in range(1,len(s)):
    	# 두 정수의 차>1면 두 정수 사이에 다른 정수가 존재
        if s[i]-s[i-1] > 1:
            print(s[i-1]+1)
            break

도저히 그리디알고리즘으로는 문제를 풀 방법이 생각나지 않아 조합을 이용하여 풀었다. 우선 combination()을 통해 모든 조합을 구하고 이를 통해 구할 수 있는 모든 정수를 구한다. 이후 가장 작은 정수가 무엇인지 찾는다. 

 

정답코드

# 그리디
n = int(input())
data = list(map(int, input().split()))
data.sort()

target = 1
for x in data:
    if target < x:
        break
    target += x
print(target)

그리디 알고리즘으로 아주 깔끔하게 해결 했다. 아이디어는 다음과 같다.  'target이 주어졌을 때, 1부터 target-1까지는 반드시 만들 수 있다.' 따라서 target을 계속 업데이트 하면서 해당 target을 만들 수 있는지 확인한다. 

주어진 화폐 단위 [1,2,3,8]일때 다음을 살펴보자.

1. target = 1, 화페 단위 1이 존재함으로 가능 -> target = 1 + 1 = 2 (2 이전의 모든 수는 표현이 가능하다는 의미)

2. target = 2, 화페 단위 2이 존재함으로 가능 -> target = 2 + 2 = 4(4 이전의 모든 수는 표현이 가능하다는 의미)

3. target = 4, 화페 단위 3이 존재함으로 가능 -> target = 4 + 3 = 7(7 이전의 모든 수는 표현이 가능하다는 의미)

4. target = 7, 다음 화페 단위는 8로 7을 만들 수 없음 -> 정답은 7

---

이 문제가 정말 그리디 알고리즘 문제인 것같다. 지금까지 문제들은 그냥 보면 그리디 알고리즘이네 단순하게 생각하면 되겠다! 하지만 지금 이 문제는 그리디알고리즘 문제인지 전혀 알지 못했고 그리디 알고리즘 파트에 있기 때문에 그리디 알고리즘으로 풀 수 있지 않을까 싶어서 접근하려고 해도 접근조차 하지 못한 문제였다. 역시 다양한 문제를 풀면서 그리디 알고리즘 유형에 익숙해지는 방법 밖에 없는 것 같다.

 

고등학교 시절이 생각나는 것 같다. 고1 때까지만 해도 어떻게 이런 문제를 풀지했던 문제들이, 고2 때 풀리고 이때도 안된다면 고3때 풀리고 결국은 다양한 문제를 접하면 경험치가 쌓여가는 것이 중요한 것 같다. 나의 코딩 실력을 논하기에는 아직 나의 경험치가 많이 부족한 것 같다. 그렇기에 지금 이 문제가 안풀린다고 낙담할 필요도 없다.

"이런걸 어떻게 풀어가 아니라 이런 문제를 자주 접해서 익숙해지자."