문제
동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍멍이보다 키가 작기 때문에 멍멍이를 쓰다듬어줄 수 없다. 원숭이가 멍멍이를 쓰다듬으려면 둘의 키가 같아야 하기 때문이다.
그래서 원숭이는 그 날부터 자신의 키를 조절하기로 마음먹었다. 원숭이는 초능력자이기 때문에 마음대로 키를 늘릴 수 있다. 하지만 안타깝게도 사람이 아니라 동물이기 때문에 하루에 늘릴 수 있는 키의 양을 1cm밖에 조절할 수 없다. 예를 들어 오늘 키를 5cm 만큼 늘렸다면, 내일은 키를 4cm, 5cm, 6cm 중 하나만큼 키를 늘릴 수 있다는 뜻이다. 늘릴 수 있는 키의 양은 음수가 될 수 없다. 그리고 첫째 날과 마지막 날에는 무조건 1cm 만큼 늘릴 수 있다.
현재 원숭이와 멍멍이의 키가 주어졌을 때, 원숭이가 매일 키를 늘려서 멍멍이와 키가 같아지는 최소의 일수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 원숭이의 키 X와 멍멍이의 키 Y가 주어진다. X, Y는 0 ≤ X ≤ Y < 231을 만족하는 정수이다.
출력
첫째 줄에 원숭이가 멍멍이의 키와 같아지게 되는 최소의 일수를 출력한다.
풀이 및 회고
풀이
원숭이와 멍멍이의 키 차이를 나열하다 보면 규칙이 보인다. 처음과 끝은 무조건 1이어야 하므로 차이가 3일경우 '1 1 1', 4일 경우 '1 2 1', 5일 경우 '1 2 1 1', 6일 경우 '1 2 2 1'과 같은 형태로 나타난다. 이를 for문을 통해 적절한 구간을 찾고 길이를 출력하면 된다.
회고
처음에는 DP?로 풀려다가 '틀렸습니다' 맞고서 수학?으로 틀어서 푼 문제이다. 물음표가 붙어 있는 이유는 내가 쓴 그 코드가 과연 DP가 맞는가? 수학이 맞는가? 라는 생각때문에.. 아직도 내가 푼 방식이 제대로 된 방식인지는 모르겠다.. 그렇지만? 다른 사람 코드보기는 귀찮으니까..
코드
monkey, dog = map(int, input().split())
remaining = dog - monkey
if remaining == 0:
print(0)
elif remaining == 1:
print(1)
elif remaining == 2:
print(2)
else:
for i in range(1, 100000000):
if i * (i + 1) < remaining <= i * (i + 1) + (i + 1):
print(i * 2 + 1)
break
if i * (i + 1) + (i + 1) < remaining <= (i + 1) * (i + 2):
print(i * 2 + 2)
break
