링크 : 백준 2437번 : 저울
주어진 N개의 무게추들을 사용해서 측정할 수 없는 최소 무게를 출력하는 문제다.
ex) 1, 2, 3, 10 이 주어진다면 7이 답이 된다.
설계
문제의 해결방법이 바로 떠오르지 않아서 일단 예시들을 생각해봤다.
예를 들어, 입력으로 10, 1, 3, 2 이 주어질 때, 1,2,3,4,5,6까지 측정가능하고 7에서 측정 불가능하다는 것을 확인할 수 있어야 한다.
그렇게 하려면 1,2,3,10 순, 즉 오름차순으로 접근할 수 있어야 한다.
따라서, 입력 순서대로 계산에 집어넣는 것은 최적해로 이어질 수 없다.
가장 작은 무게의 추를 꺼내는 것부터 시작해야 할 것 같다.
그 다음으로 생각해낸 것이 현재 측정가능한 구간을 구하는 것이다.
아래에 예를 살펴보자.
w = [1, 1, 2, 3, 9...] 를 입력받았을 때
w[0]만 사용해서 측정할 수 있는 무게의 구간은 1 ~ 1이다.
w[0], w[1]을 사용하면 1 ~ 2 ,
w[0], w[1], w[2]를 사용하면 1 ~ 4,
w[0] ~ w[3]까지 사용하면 구간은 1 ~ 7로 확장된다.
문제는 w[4]를 추가할 때 발생한다.
구간이 1 ~ 7 과 9 ~ 16 로 분리되기 때문이다.
즉, 구간의 불연속은 지금까지 측정가능했던 구간의 최대값과
새로운 추의 무게가 불연속하면 발생한다.
위의 말을 수학적으로 바꿔보면,
현재 측정 구간이 [ A, B ] 일때 새로운 추의 무게 C가
B + 1 < C이면 불연속이 발생하고, 출력해야 할 문제의 답은 B + 1이 된다.
B + 1 >= C라면 불연속이 발생하지 않으므로
구간을 [ A ,B + C ]로 갱신하고 불연속을 찾을 때까지 진행하면 된다.
구현
구현은 정말 쉽다. 입력의 크기도 1000으로 작은 편이니 맘편히 리스트로 입력받아서 오름차순으로 정렬한다.
N = int(input())
#입력
weights = list(map(int,input().split()))
#오름차순 정렬
weights.sort()그리고 설계에서 말한 현재 측정가능한 무게의 닫힌 구간을 나타낼 리스트를 선언한다.
수학에서 닫힌 구간을 대괄호로 표현하니 마침 잘 됐다.
#잴 수 있는 무게의 범위
Range = [0,0]벌써 끝나간다.
반복문을 통해 작은 무게의 추부터 탐색하며 아래 과정을 반복한다.
- B + 1 < C : 불연속 발생, 반복문 종료
- B + 1 >= C : Range를 [ A , B + C ]로 갱신
코드로는
for el in weights:
#범위의 불연속이 발생할 경우
if Range[0] + el > Range[1] + 1:
break
#범위가 계속 이어질 경우
else :
Range[1] += el반복문이 종료되었을 때, 결과는 ( Range의 최대값 + 1 )이 된다.
이것은 설계에서 이미 확인했다.
전체코드
N = int(input())
#입력
weights = list(map(int,input().split()))
#오름차순 정렬
weights.sort()
#잴 수 있는 무게의 범위
Range = [0,0]
for el in weights:
#범위의 불연속이 발생할 경우
if Range[0] + el > Range[1] + 1:
break
#범위가 계속 이어질 경우
else :
Range[1] += el
#끊어진 부분에서 1 더한값이 답
print(Range[1] + 1)오랜만에 설계로 끝나는 문제를 풀어본 것 같다.
요즘 DP를 많이 풀어보느라 구현이 복잡한 문제가 많았는데
간명하게 끝나는 문제를 풀고나니 괜히 기분이 좋다.
