[백준/파이썬] 2437: 저울

문제 보러 가기!!!

예전에 틀린 코드💫

DFS로 풀려고 했던 듯. 예제는 맞추는데, 채점을 하면 메모리 초과가 난다.

import sys
sys.setrecursionlimit(10**6)

def DFS(depth,score):
    if depth==k:
        if score>0:
            A.append(score)
    else:
        DFS(depth+1,score+L[depth])
        DFS(depth+1,score)

if __name__ == "__main__":
    k=int(input())
    L=list(map(int,input().split()))
    A=[]
    DFS(0,0)
    A=list(set(A))
    for i in range(1,max(A)):
        if i not in A:
            print(i)
            break

정답 코드 💟

아이디어가 정말 안 떠올라서, 다른 분의 풀이를 봤다.
보고 나니, 참신했다.. 이해는 잘 되는데, 아이디어는 나 혼자서는 못 떠올렸을 것 같다..

주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 구해야 한다. 양의 정수 무게니까 무게는 1부터 가능한지 쭉~ 보면 된다.
추를 순서대로 봐주면서, 그때까지의 추들로 무게를 쭉~ 만들 수 있는지 봐준다. 무게를 쭉~ 만들 수 있다면(중간에 양의 정수를 건너뛰지 않고. 즉 무게 1은 만들 수 있는데 2는 못 만들고 3은 만들 수 있으면 X. 무게 1, 2, 3을 각각 다 만들 수 있으면 OK) now_num에다가 추의 무게를 누적합을 해줬다.

그때까지의 추들로 무게를 쭉~ 만들 수 있는지 판단은 어떻게 하냐면,,,
일단 주어진 추들을 오름차순으로 정렬해둔다. now_num은 그때까지 쓴 추들로 측정할 수 있는 무게이다. 처음에는 아무 추도 안 쓰니까 0이다.
(이제 오는 추의 무게)가 (now_num+1) 이하이면, 그때까지 추들+이제 오는 추로 (now_num+이제 오는 추의 무게)까지 표현이 가능한 것이다.

예를 들어서, 지금까지 있는 추들로 1, 2, 3, 4, 5가 표현 가능한데, 이제 오는 추가 7이라면 6은 못 만드니까 안된다. 만약에 이제 오는 추가 6이라면 1, 2, 3, 4, 5 는 기존에 있던 추들로 만들 수 있었고, 이제 오는 추로 6도 만들 수 있고, 기존 추와 이제 온 추를 같이 쓰면 무게 7(1+6), 8(2+6), 9(3+6), 10(4+6), 11(5+6)도 만들 수 있다.

쭉 ~ 보다가 있는 추들을 다 사용했거나, 중간에 그때까지의 추들로 무게를 쭉~ 만들 수 있지 않게 되면!!(예- 3까지 무게를 표현할 수 있었는데, 이제 온 추가 5이면 4를 표현 못하게 됨) 그때까지의 now_num에 1 더한 것을 출력하면 정답! (now_num까지는 측정 가능하니까 now_num + 1)

import sys

input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
arr.sort()

now_num = 0
for i in range(N):
    if arr[i] <= now_num + 1:
        now_num += arr[i]
    else:
        break
print(now_num + 1)