99클럽 코테스터디 9일차 TIL - 백준 2437

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

해당 문제는 풀다가 도저히 이해가 안가서 풀이를 보고 이해해보고자 했다 🥲

알고리즘 분류를 보니, 그리디 알고리즘을 활용하여 푸는 문제라고 하는데 왜 이게 그리디 알고리즘인지는 아래에서 알아보도록 하자.

우선 이 문제를 푸는 방법이다.

 

https://aerocode.net/392

 

이분의 풀이를 참고했는데, 해당 풀이를 이해한 바는 다음과 같다.

 

1) "추들을 가지고 측정할 수 있다" = "추를 활용하여 ~ 범위 내의 무게를 측정할 수 있다" 라는 의미로 이해한다.

 --> 측정할 수 있는 범위를 수직선으로 그려보기

2) 무게가 작은 추를 활용하여 측정할 수 있는 무게를 점점 늘려가야하므로, 추들을 오름차순으로 정렬 후 차례대로 올려본다.

 

3) 무게가 낮은 추부터 올려가며 측정할 수 있는 범위를 그려본다. 그림에서 3번까지의 예시를 들어보면

첫번째 추: 0~1까지의 범위 측정 가능

두번째 추: 1~2까지의 범위 측정 가능하므로, 앞 범위와 합쳐 0~2까지의 범위 측정 가능

세번째 추: 2~4까지의 범위 측정 가능하므로, 앞 범위와 합쳐 0~4까지의 범위 측정 가능

네번째 추: 3~7까지의 범위 측정 가능하므로, 앞 범위와 합쳐 0~7까지의 범위 측정 가능

이렇게 진행했을때, 20 이후가 처음 끊기는 지점이므로 측정할 수 없는 최소 범위는 21이 된다.

 

즉, 추를 차례대로 더한 여태까지의 총합이 특정 추보다 작을 경우, 총합 + 1 가 추로 측정할 수 없는 수의 최소값이 된다.

 

4) 이를 코드로 나타내면 다음과 같다.

 

✅ 풀이

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

answer = 0  # 지금까지 측정 가능한 최대 무게 (초기: 0)

for w in arr:
    if w > answer + 1:
      break
    answer += w  # 기존 구간 확장

print(answer + 1)  # 끝까지 연결되었으면 다음 숫자부터 측정 불가

 

💡 해당 문제가 그리디 알고리즘인 이유

 

1) 그리디 알고리즘이란?

- 눈앞에 보이는 최선의 선택을 하며 문제를 해결하는 알고리즘

- 최적 부분 구조: 부분해를 푸는 과정이 곧 최적해를 구하는 과정과 일치한다.

- 그리디 선택 속성: 선택 과정이 다른 과정에 영향을 주지 않는다.

 

2) 위 내용에 따라 해당 문제가 왜 그리디 알고리즘인지를 파악해보면

- 눈앞에 보이는 최선의 선택 ==> '정렬된 추에서 매 순간 지금까지 측정할 수 있는 추의 무게를 고려한다'

- 최적 부분 구조 ==> 각 단계마다 측정할 수 있는 무게 범위를 알면 (부분해 푸는 과정) 측정할 수 없는 범위를 알 수 있다.

- 그리디 선택 속성 ==> 작은 추부터 사용해서 가능한 무게 범위를 확장하는 것(선택 과정)이 이후의 과정에 영향을 주지 않는다.

 

❗️이 문제가 그리디 알고리즘인지를 어떻게 판별할 수 있을까?

사실 해당 문제가 그리디 알고리즘으로 푸는거라고 파악하기가 쉽지 않은데, 고수분은 소거법과 같은 형태로 알고리즘을 파악하신다고 한다.

 

첫번째로, 완전 탐색을 고려한다.

- 모든 추의 조합의 합을 구하여 완전 탐색하는 방법 --> N이 1,000 이므로 시간초과 발생 (내가 시도했던 방법임..)

 

두번째로, DP를 고려한다.

- DP는 수의 범위대로 배열을 만드는 방식인데, N이 1,000이며 무게가 최대 1,000,000 까지 이므로 최악의 경우 10억의 원소를 담을 배열 공간이 필요함 --> 메모리 초과 발생

- 명확한 점화식을 세우기가 어렵다.

 

세번째로, 이분탐색을 고려한다.

- 타겟하는 조건의 값을 특정할 수 없기 때문에, 이분탐색으로 풀 수는 없음

 

네번째로, 백트래킹을 고려한다.

- 가지치기할 수 있는 조건이 모호함

 

그럼 그리디로 풀 수 있을까? --> 부분해를 구해 나가는것이 곧 최적해를 구하는 과정과 일치하는구나 --> 그리디로 사고