백준 2437 - 파이썬

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

2437번: 저울

문제해결

가장 먼저 입력된 추들을 무게 순으로 오름차순 정렬 후, 가장 작은 추부터 차례대로 더해봤다. 하지만 감이 잡히지 않아 추를 앞뒤만 합한 경우, 3 ~ n개 묶어서 합한 경우 등 생각나는 방법들은 다 해 봤다. 하지만 답을 찾기 어려웠고, 다른 사람의 풀이를 찾아봤다.

 

이 사람 역시 풀지 못해 다른 사람의 풀이를 참고하였다고 한다. 이 사람의 풀이를 보면서 나의 실력이 조금만 더 높이 뛰면 허들을 넘을 수 있지만 아직 부족해 발끝이 걸리는 수준이라는 느낌을 받았다. 조금만 더 접근하면 풀 수 있을거 같은데 그러지 못하는 점이 매우 아쉽다.

 

이 사람의 풀이 핵심은 다음과 같다.

 

예를 들어 [1, 2, 2] 라는 추로 측정할 수 있는 무게는 닫힌구간 [1, 5]이다. 여기서 5는 모든 추를 더한 값이다.

 

여기서 3이라는 추가 추가된다면 새로 측정 가능한 범위는 [1+3, 5+3]이므로 8까지 측정이 가능하다. 여기서 10을 추가했을때 새로 측정 가능한 범위는 [4+10, 6+10]이다. 따라서 [14, 16]라는 구간을 새로 측정 가능해진다. 여기서 측정 가능한 범위는 [1, 8]과 [14, 16]이다.

 

여기서 우리는 규칙성을 찾을 수 있다. [1, k]에서 k의 값보다 더 큰 추가 들어온다면 측정할 수 없는 구간이 생긴다는 점이다. 따라서 측정할 수 없는 무게의 최소값은 k+1이 되는 것이다.

 

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline

n = int(input())
weights = list(map(int, input().split()))
weights.sort()

target = 1

for weight in weights:
    if target < weight:
        break

    target += weight

print(target)

이 문제를 풀때 컴퓨팅적 사고로 풀려고 노력해봤다. 이전에는 추상적인 방법만 찾고 구현하려는 경우가 많아서 접근하는데 어려움이 있었는데, 이번에는 생각보다 많이 해답에 접근할 수 있었던거 같다. 코딩은 추상적인 아이디어 속에서 규칙성을 찾고, 이를 코딩으로 구현하여 현실화 하는 것이 중요한거 같다. 또한 참고한 블로그에도 나온 말이지만 복잡해 보이는 문제가 그림으로 표현하면 매우 간단해질수 있다는 점이다. 그리디 문제를 풀때 꼭 상기시켜야 할 문장인거 같다. 앞으로 계속 꾸준히 문제를 스스로 생각하면서 최대한 풀다보면 지금보다 실력이 많이 오를거 같다.