[그리디/백준] 2437번: 저울

-문제 : https://www.acmicpc.net/problem/2437

 

Gold Level2 문제

2022.11.01에 풀이 추가

 

풀이 이해

간단하지만 도무지 이해가 가지 않아서 구글링을 했다.

풀이 아이디어는 weights[i]가 추가될 때마다 측정 가능한 무게의 범위가 증가하는데, 이게 연속적일 수도 아닐 수도 있다. 

그래서 새로 추가된 부분이 연속적이지 않을 때, 그때의 시작 부분을 반환하면 된다

참고한 블로그

 

-정답풀이: 

이 문제도 그리디에서 변수에 값 저장한 후 단일 반복문으로 푸는 문제다 

이 유형 문제는 언제쯤 답 없이 풀 수 있을까ㅠㅠㅠㅠ 풀고 싶다 

n=int(input())
data=list(map(int,input().split()))
data.sort()
result=0

for i in range(n):
    if result + 1 >= data[i]:
        result += data[i]
    else:
        break
        
print(result+1)

 

-메모리 초과한 풀이

combination으로 모든 경우의 수를 구하고, 그것의 합을 구한 다음, 그 중에 없는 가장 작은 값을 출력하는 방법을 생각했다.

역시나 메모리 초과가 떴다 

import itertools

n=int(input())
data=list(map(int,input().split()))
result=[]
for i in range(n):
    result.append(data[i])

for i in range(2,n):
    temp = list(itertools.combinations(data,i))
    for j in range(len(temp)):
        result.append(sum(temp[j]))
    
    
result.sort()
i=1
while True:
    if i not in result:
        answer=i
        break
    i+=1
print(answer)