백준 2437 저울 파이썬

dasd412·2022년 6월 3일
0

코딩 테스트

목록 보기
45/71

문제 설명

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.

입력 조건

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

출력 조건

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.


전체 코드

import sys

n = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()

# 현재 커버 범위 = (시작 , 끝), 처음에는 0 ~ 0으로 초기화한다.
current = [0, 0]

answer = 0

for i in range(len(arr)):
    # 다음 구간 커버 범위 = (현재 시작 + 다음 추, 현재 끝 + 다음 추)
    next_start = current[0] + arr[i]
    next_end = current[1] + arr[i]

    # 현재 끝 +1 < 다음 시작이면 끊어지는 범위가 생긴 것이다. 따라서 측정할 수 없는 구간이 발견됬다.
    if current[1] + 1 < next_start:
        answer = current[1] + 1
        break
    # 현재 끝 + 1>= 다음 시작이면, 겹치거나 접하는 부분이 있으므로 측정할 수 있는 구간이다. 이를 [0,next_end]로 바꾼다.
    else:
        current = [0, next_end]

# 끝까지 끊어진 구간이 없다면, 마지막 끝 +1이 표현할 수 없는 최소의 양수다.
if answer == 0:
    print(current[1] + 1)
else:
    print(answer)

참고

https://aerocode.net/392


예시 설명

1

2 
2 3

의 경우, 답은 1이다.

처음에는 0 ~ 0으로 되어 있었다. 그리고 추의 무게 2를 더하면, 2 ~ 2가 무게의 커버 범위가 된다. 0+1<2 이므로 커버할 수 없는 범위이다. 따라서 답은 1.

2

2
1 2

의 경우 답은 4이다.
그림으로 살펴보면 다음과 같다.

처음에는 0 ~ 0만 갖고 있다.

다음 추 1을 더하면, 1 ~ 1가 되고, 0+1 == 1이므로 0 ~ 1의 구간이 된다.

다음 추 2를 더하면, 0+2 ~ 1+2 -> 2 ~ 3의 구간이다.

1+1<=2이므로 겹치는 구간으로 판정한다. 따라서 0~3 구간으로 칠 수 있다.

더 이상 무게를 달 것이 없다. 0~3 구간까지는 커버했으므로 3+1=4가 커버할 수 없는 무게이다.


그리디 + 배열, 그리디 + 우선 순위 큐 말고 다른 풀이로 해야했던 그리디이다.
구간 + 그리디 유형이라 볼 수 있다.

profile
아키텍쳐 설계와 테스트 코드에 관심이 많음.

0개의 댓글