작심큰일 챌린지 - Day 3. 저울 (미들러, Python)

출처 - 작심큰일 챌린지 메인 페이지

 

벌써 3일째가 되었다.

 

하루 1문제씩 꾸준히 문제풀이하는 습관을 형성한다는 목표를 위해서 꾸준히 글을 작성하고 노력해 보자.

 

---

Day 3. 저울

 

오늘의 문제는 백준 프로그래밍 2437번 문제다.

 

문제

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

 

 

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

 

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

 

입력

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

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

예제 입력 1

7
3 1 6 2 7 30 1

예제 출력 1

21

 

 

---

풀이 과정

 

"무게추의 최솟값"을 구해야 하는 문제라는 걸 본 순간 그리디 알고리즘이 떠올랐다.

 

개인적으로 어떤 시나리오에서 최적의 경우를 찾아야 하는데 최적의 경우가 값의 합 같은 경우는 무조건 그리디 알고리즘 같다.

 

문제를 많이 안 풀어봐서 그런가... 아직까진 예외가 되는 경우를 못 봤다.

 

가장 대표적인 "거스름돈" 문제를 기반으로, 알고리즘의 기본적인 흐름을 잡았다.

 

1. 입력받은 값을 배열의 형태로 저장
2. 저장된 값을 정렬 (sort)
3. 타겟값을 구하기 위해 각 경우의 수를 순회하며 비교
4. 최솟값을 찾으면 탐색을 종료하고 print

 

여기서 한 가지 문제가 발생했다.

 

기존의 그리디 탐색법에서는 타겟값을 매개변수로 전달받는 (i.e. 2400원 = 타겟값 을 받았을 때 거스름돈) 가정의 문제들이었지만, 현재 문제에서는 타겟값이 하나로 고정되어 있고 직접 찾아야 했다.

 

꽤 고민했지만, 타겟값을 구하기 위한 방법으로 다음과 같은 접근이 가능하다.

 

1. 타겟값은 1부터 시작
2. 각 추를 순회하며, 현재 타겟값으로 만들 수 있는지 여부를 확인
  a. 현재 추의 무게가 타겟값 이하이면 타겟값의 범위를 확장
  b. 추의 무게가 타겟값을 초과했으면 타겟값(= 현재 추의 무게 +1)이 측정할 수 없는 최솟값, 순회 종료

 

몇 가지 전제 조건에서 위 로직은 무조건 맞을 수밖에 없다.

 

1. 주어진 무게 추들이 오름차순으로 정렬되어 있어야 한다.
2. 현재 추의 무게가 타겟값 이하일 때만 누적이 된다.
3. 구간이 끊기기 전까지는 연속적 조합이 항상 가능하다.

 

조금 헷갈렸던 부분은 "어떻게 타겟값이 추의 무게만큼 증가하는데 중간의 수는 무조건 만들 수 있는가?" 였다.

 

조금만 생각해 보면 알 수 있는데, 타겟값이 추의 무게만큼 증가하기 때문이다.

 

예를 들어, [1, 2, 5]라는 정렬된 추들이 있다면 다음과 같은 순서를 따른다.

 

1. 타겟값 1로 시작
2. 첫 번째 무게추 1은 타겟값(1) 이하이므로 통과, 타겟값을 추의 무게(1)만큼 확장 = 타겟값은 2
3. 두 번째 무게추 2는 타겟값(2) 이하이므로 통과, 타겟값을 추의 무게(2)만큼 확장 = 타겟값은 4
4. 세 번째 무게추 5는 타겟값(3)을 초과하므로 통과 실패, 현재 타겟값이 만들 수 있는 최솟값
5. 1~3까지는 모두 만들 수 있는 조합 (1, 2, 3(1+2))이지만, 4는 주어진 무게추들로는 만들 수 없음 = 현재 타겟값이 최솟값

 

또한, 타겟값이 1로 시작했기 때문에 조합할 수 있는 무게추들보다 항상 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 weight <= target:
    target += weight
  else:
    break;

print(target)

 

그리디 알고리즘 자체가 단순해서 코드 작성 자체는 쉬웠던 것 같다. 

 

핵심은 기존의 그리디 알고리즘과 다르게 "타겟값 매개변수로 주어지지 않은 경우 어떻게 직접 찾을 것인지"에 대한 접근이었다.

 

---

개선점

코드 자체는 시니어 해설과 동일했다. 오호이!

 

다만 코드 구현 과정에서 최적화가 잘 되었는지, 어떻게 해야 좀 더 최적화할 수 있을지 고민해보지 못했던 것 같다.

 

이번 해설의 최적화 팁은 다음과 같았다.

 

1. 정렬우선: 가추를 작은 값부터 사용해야 그리디 전략이 제대로 작동할 수 있어
2. target 누적만으로 해결: 별도의 배열이나 조합 계산 없이, 누적합만으로 측정 가능한 범위를 관리할 수 있어
3. 빠른 종료 전략: target보다 큰 수가 나오면 바로 종료하면 되니까, 불필요한 반복 없이 성능도 좋아

 

그냥 이전 그리디 알고리즘의 코드를 기반으로 작성했는데, 최적화 방식과 들어맞은 느낌이다.

 

처음 그리디 알고리즘을 배울 때 해당 코드가 최적의 코드인지 생각해보지 못한 점이 아쉬웠다.

 

또한, 코드의 핵심 포인트가 무엇인지 스스로 정리해 보는 것이 중요한 것 같다.

 

1. 타겟(답)을 직접 구해나감
2. 정렬 → 누적합(현재 가능한 최대 범위) → 조건 위배 시 즉시 종료 및 답 출력

 

이번 문제의 핵심은 위 두 가지였다고 생각한다.