1. 문제
2. 풀이
완전탐색 기반으로 풀이할 방법이 생각나지도 않을 뿐더러, 설사 어떻게 생각해낸다 하더라도 경우의 수가 너무많다.
따라서 Greedy로 풀어야한다.
이름부터 사악한 Greedy 알고리즘이란, 지역적인 최적값 선택의 연속이 글로벌한 최적값으로 이루어진다는 것인데
실제 문제를 풀어보면, 그냥 알아서 잘 짜야한다. 나는 흡사 IQ 테스트같다고 생각한다.
따라서 Greedy한 알고리즘을 만들 때 가장 중요한 것은
코드가 너무 많은 if문으로 case를 나누지 말아야한다.
그러면 일단 Greedy하지 않을 뿐더러, 무엇보다 우리가 푸는 문제가 누군가에 의해 만들어졌다는 것을 고려할 때, 코드가 지저분하게 케이스를 나누고 있다면 접근방식이 잘못 되었을 가능성이 농후하기 때문이다.
2.1. Greedy 풀이
테스트케이스가 다 오픈된 상황에서조차 몇 시간동안 끙끙대서 겨우 풀어낸 터라,
솔직히 시험장에서 시간내에 풀이하라면 자신이 없다.
[ Greedy 풀이 ]
- 주어진 나무 리스트를 탐색하며 다음 변수를 계산한다
- tt_diff == 총 키워야할 나무의 높이
- odd == 홀수만큼 키워야할 나무의 갯수
- 그리고 총 키워야할 나무의 높이(tt_diff)를 키울 수 있는 이상적인 최단기간을 계산한다
위 표에서 볼 수 있는 것처럼, 각각 tt_diff에 대한 이상적인 최단기간(days)이 규칙성을 가진다.days = (tt_diff // 3) * 2 + (tt_diff % 3)
- 구한 최단기간까지, 1만큼 자라는 물을 준 날(one)과, 2만큼 자라는 물을 준 날(two)를 센다.
예를 들어, days == 5 라면, '1 2 1 2 1'이므로, one = 3이고 two =2이다.one = days // 2 + days % 2two = days // 2
이제 홀수만큼 자라야할 나무의 개수가 몇개냐에 따라 답을 다르게 구할 수 있다.
짝수만큼 자라야 할 나무는 중요하지 않다. 왜냐하면 짝수만큼 자라야할 날의 경우, 총 합이 그 숫자 이상이라면 주어진 1, 2의 조합이 어떻든지 상관없이 정확히 숫자를 맞출 수 있다.
반대로 홀수만큼 자라야할 날에는 반드시 하나의 1이 존재해야 홀수를 만들어낼 수 있다.
Example) 7 = (1, 1, 1, 1, 1, 1, 1) or (1, 1, 1, 1, 1, 2) or (1, 1, 1, 2, 2) or (1, 2, 2, 2)
따라서 이상적인 최단기간까지 포함된 one(1의 물을 주는 날의 갯수)이 odd(홀수만큼 자라야 하는 나무 갯수)이상이라면, 필요한 1의 갯수가 모두 확보되었으므로 이상적인 최단기간이 곧 답이다.
반대로 one > odd라면 총 물의 양은 충족되었는데 one의 갯수가 부족하다는 말이므로, 필요한 1의 갯수(=odd)가 충족되는 날이 최단기간이다.
- odd <= one 라면
- result 는 위에서 구한 days(이상적인 최단기간)이다.
result = days
- result 는 위에서 구한 days(이상적인 최단기간)이다.
- odd > one f라면
- result 는 odd번째로 1의 물을 주는 날이다.
result = 2 * odd -1
- result 는 odd번째로 1의 물을 주는 날이다.
import sys
sys.stdin = open('input.txt', 'r')
T = int(input())
for t in range(1, T + 1):
N = int(input())
trees = list(map(int, input().split()))
the_tallest = max(trees) # 가장 큰 나무의 값
tt_diff = 0 # 총 자라내야할 나무의 높이를 구할 변수
odd = 0 # 자라내야할 나무의 높이가 홀 수인 경우를 카운팅할 변수
for tree in trees:
diff = the_tallest - tree # diff == 현재 나무의 자라내야할 높이
tt_diff += diff # tt_diff 업데이트
if diff % 2: # diff가 홀수이면, odd += 1
odd += 1
days = (tt_diff // 3) * 2 + (tt_diff % 3) # days == tt_diff에 대한 이상적인 최단기간
one = days // 2 + days % 2 # days까지 watering == 1인 날
two = days // 2 # days까지 watering == 2인 날
if odd <= one: # 홀수 높이 차의 나무 갯수 <= 이상적인 최단기간까지 watering == 1인 날의 수
result = days # 답은 이상적인 최단기간
else: # 홀수 높이 차의 나무 갯수 > 이상적인 최단기간까지 watering == 1인 날의 수
result = 2 * odd - 1 # 답은 odd번째 watering == 1이 나오는 날
print(f'#{t} {result}')