[백준] 2437번 저울 - 파이썬/그리디

https://www.acmicpc.net/problem/2437

1차 풀이 (시간 초과)

import sys

N = int(input())

N_list = list(map(int,sys.stdin.readline().split()))

N_list.sort()

def check(N_list):
    sum_list = []
    for i in range(0,len(N_list)):

        if len(sum_list):
            temt = sum_list[:]
            for j in range(len(temt)):
                temt[j] = temt[j] + N_list[i]
            sum_list += temt

        sum_list.append(N_list[i])

        sum_list = list(set(sum_list))
        sum_list.sort()
        print(sum_list)
        for j in range(1,len(sum_list)+1):
            if j != sum_list[j-1]:

                return j

print(check(N_list))

추가 A,B,C,D 4개가 있다고 가정했을때

추가 1개인 경우 A만 측정 가능하다.

측정 가능한 무게 = A

그런데 여기에 B가 추가되면 이 전의 측정 가능한 무게 리스트 원소에 B를 다 더해준 값과 추가된 무게 B만큼 측정이 추가로 가능해진다.

측정 가능한 무게 = A , A+B, B

마찬가지로 C가 추가될경우

측정 가능한 무게 = A, A+B, B, A+C, A+B+C, B+C, C

이러한 로직으로 코드를 짰는데 시간 초과가 발생하였다.

그런데 단계별로 측정 가능한 무게 리스트를 보니까

원소의 최대값이 분기점이였다.

이걸 토대로 코드를 다시짜서 통과했다.

2차 코드

import sys

N = int(input())

N_list = list(map(int,sys.stdin.readline().split()))

N_list.sort()


start = 1

while True:

    if N==1 or N_list[0] != 1 :
        print(1)
        break


    check_num = sum ( N_list[:start] )+1

    if check_num < N_list[start]:
        print(check_num)
        break

    start +=1

    if start == len(N_list):
        print(sum(N_list)+1)
        break

추가 [1 1 2 3 6 7 30] 있다고하면

[1 1 2 3 6]으로는 최대 13까지 측정가능하고 14를 판별해야한다.

그런데 이 14를 만들기 위해서는 [1 1 2 3 6] 보다 오른쪽에 있는 [7 30] 숫자를 사용해야 한다.

다행히 14가 7보다 크므로 7을 활용하면 14를 만들 수 있다.

그런데 [1 1 2 3 6 7]으로는 최대 20까지 측정 가능하고 21을 판별해야하는데

7 오른쪽에 있는 숫자가 30이라 21보다 크므로

[1 1 2 3 6 7] 로는 21을 만들 수가 없다.

이러한 로직으로 코드를 작성하였고

추가 1개이거나 가장 가벼운 추의 무게가 1보다 클때는 답이 무조건 1이므로 예외 조건을 추가했다.