문제 요약 및 풀이
문제 상황을 요약하면 다음과 같다.
1
2
3
4
5
자연수 a,b,c 가 주어진다.
주어진 자연수 a, b, c중 2개를 골라 1씩 더할 수 있다.
이때, 모든 숫자를 같게 만들기 위한 최소 덧셈 횟수는 몇번인가?
풀이 코드
문제를 보자마자, 바로 드는 생각은
그때 그때 가장 작은 숫자 2개를 골라 1씩 더해주면서 카운팅하면 되지 않을까? 였다.
그래서 바로 아래와 같은 풀이를 작성했다.
1
2
3
4
5
6
7
8
9
l = [int(input()) for i in range(3)]
cnt = 0
while not l[0] == l[1] == l[2]:
l.sort()
l[0] += 1
l[1] += 1
cnt += 1
print(cnt)
(브론즈 2티어 문제라서 그렇게 어려운 풀이를 유도하지는 않을 거라 생각했고, 범위도 신경쓰지 않는 풀이를 작성해버렸다.)
역시 위 풀이는 시간초과가 발생했고, 시간초과를 보고 나서 a, b, c의 최대 범위가 5억이라는 것을 확인했다.
그래서 이제 간단하게 또 생각을 틀었다.
가장 작은 2개가 서로 같지 않다면 그 두 개를 격차만큼 더해주고, 같다면 가장 큰 수와의 격차를 더해주면 되지 않을까?
그리고 아래와 같은 풀이를 작성했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
l = [int(input()) for i in range(3)]
cnt = 0
while not l[0] == l[1] == l[2]:
l.sort()
if l[1] != l[0]:
diff = l[1] - l[0]
else:
diff = l[2] - l[1]
l[0] += diff
l[1] += diff
cnt += diff
print(cnt)
하지만… 여기서 끝나지 않았다..
바로 아래와 같은 케이스에서 너무나 늦게 답이 수렴되었기 때문이다.
1
2
3
1
499999999
500000000
다시 한번 생각을 틀었다.
무조건 작은 2개를 뽑는 게 아니라,
먼저 큰 두 숫자의 격차를 더해주고, 그 두 숫자가 같다면(격차가 0이라면) 작은 2개의 격차를 더하자.
1
2
3
4
5
6
7
8
9
10
l = [int(input()) for i in range(3)]
cnt = 0
while not l[0] == l[1] == l[2]:
l.sort()
diff = l[2] - l[1] if l[2] - l[1] else l[1] - l[0]
l[0] += diff
l[1] += diff
cnt += diff
print(cnt)
단순하게 어떤 숫자를 선택해야 격차를 빨리 좁혀서 더해나갈 수 있을지 생각을 했고, 요렇게 AC를 받았다.
끝