1669. 멍멍이 쓰다듬기

문제의 내용이 궁금하시다면, 아래의 링크를 확인해주세요!
문제 보러 가기

접근 과정

문제를 통해 하루에 늘릴 수 있는 키의 양은 1cm라는 정보와, 오늘 늘린 키의 양이 음수가 아닌 양의 정수 N이라면, 내일 늘릴 수 있는 키의 범위는 N - 1에서 N + 1까지의 범위라는 정보를 알 수 있었다.

또, 첫 날과 마지막 날에는 1cm만 늘릴 수 있기 때문에, 처음 생각난 것은 재귀를 이용한 풀이였다.

첫 시도

# def calc(start, end, value, day_count):
#     global count, cnt
#     cnt += 1
#     if start >= end:
#         return
#
#     if start == end - 1:
#         count = min(count, day_count + 1)
#         return count
#
#     if value > 0:
#         calc(start + (value - 1), end, value - 1, day_count + 1)
#         calc(start + value, end, value, day_count + 1)
#         calc(start + (value + 1), end, value + 1, day_count + 1)
#
# X, Y = map(int, input().split())
# count = 0xffffff
# cnt = 0
#
# if Y - X == 0:
#     print(0)
# elif Y - X == 1:
#     print(1)
# else:
#     calc(X + 1, Y, 1, 1)
#     print(count)
#     print(cnt)

첫 날에는 1cm를 더하고 시작하기 때문에, 둘째 날부터를 기준으로 늘리고자 하는 키의 양 value가 음수가 되지 않는 한에서 N - 1, N, N + 1만큼의 키를 늘리면서 재귀 호출을 진행하고, 주어진 원숭이의 키 X에 이를 더해 X가 Y 이상의 값을 가지거나, X가 Y보다 1 작은 경우 해당 시점까지 걸린 일수를 최솟값 연산을 진행하도록 하였다.

물론 이 풀이에는 치명적인 오류가 2가지 있었다.

첫째는, 주어지는 키 X와 Y의 범위가 0 <= X <= Y < 2^31 까지라는 점이었다.
저 풀이로는, 지수 시간을 아득히 뛰어넘는 시간 복잡도를 가지기 때문에, Y - X의 값이 30정도를 초과하기만 해도 매우 긴 시간이 걸리게 된다.

두번째로는, 마지막 날에 늘릴 수 있는 키는 1cm이다라는 조건을 잘못 이해했다는 점이었다.
1cm -> 2cm -> 3cm -> 4cm -> 1cm 와 같이 이전 날짜와는 무관하게 마지막 날에는 1cm만 늘린다라고 잘못 이해해버렸던 점이 실수의 원인이었다.

마지막 날에도 1cm만 늘릴 수 있다는 점은 어떤 의미를 가질까?
문제를 다시 살펴보면, 하루에 늘릴 수 있는 키의 양을 1cm밖에 조절할 수 없고, 오늘 키를 Ncm만큼 늘렸다면, 내일 늘릴 수 있는 키의 양은 N - 1cm, Ncm , N + 1cm 중 하나이다라는 조건이 있다.

여기에서, 늘릴 수 있는 키의 양의 최고 지점이 있고, 최고 지점을 기준으로 늘릴 수 있는 키의 양 N이 줄어들어 마지막 날에는 1cm가 된다라는 내용을 유추할 수 있었다!

두번째 시도

첫 시도에서의 실수를 통해 얻은 정보를 바탕으로 주어진 키 X와 Y에 대해 어떠한 규칙이 있을 것이라고 생각하게 되었고, 규칙을 파악하기 위해 키 차이 Y - X가 1일 때부터 나열해보기로 하였다.

이러한 과정을 통해, 키 차이 Y - X에 루트를 취한 값이 양의 정수 N인 경우(제곱수), 1부터 시작해서 N까지 증가했다가, 다시 1까지 감소하는 규칙을 발견할 수 있었다.

그렇다면 키 차이 Y - X에 루트를 취한 값이 양의 정수가 아닌 소숫점 값을 가지는 실수라면? 여기에도 규칙이 있지 않을까?

해당 경우에 대한 규칙을 키 차이가 9, 10, 15인 경우들에 대한 키의 증감 예시로 확인할 수 있다.
9 -> 1 2 3 2 1
10 -> 1 2 3 2 1 1
15 -> 1 2 3 3 3 2 1

키 차이 10과 15인 경우는, 10과 15보다 작은 제곱수인 9와 비교하면 다시 아래와 같이 나타낼 수 있다.
10 -> (1 2 3 2 1) + 1
15 -> (1 2 3 2 1) + 3 3

키 차이 9에서의 증감 흐름 (1 2 3 2 1)에, 1부터 3까지의 값을 적절히 더해 10부터 15까지의 증감 흐름을 나타낸 것이다.

정리하면?

• 첫째 날과 마지막 날은 무조건 1cm만 늘릴 수 있다!!
  • 따라서, 1cm로 시작해서 1cm로 끝나야 하기에, 늘릴 수 있는 키의 양의 최대 고점이 있다!
  • 1cm부터 고점까지 증가했다가, 다시 고점에서부터 1cm까지 줄어든다.
• 주어진 키의 차이 Y - X에 루트를 취한 값 N을 기준으로, 이 수가 정수와 같은지 판별한다.
  • N이 정수와 같다면, N ** 2는 키의 차이 Y - X와 동일하다.
    • 이 경우, 키는 1부터 N까지 증가하고, 다시 N에서 1까지 감소한다.
    • 예로 N이 4라면, 키의 증감은 1, 2, 3, 4, 3, 2, 1과 같다.
  • N이 소숫점 이하의 값을 가지는 실수인 경우
    • 키 차이 Y - X에서 (N의 정수 부분 ** 2)를 뺀 M을 구한다.
    • M이 N의 정수 부분보다 큰 경우
      • M을 만들기 위해서는, 1 ~ N 중 두 개의 수를 더해야 한다.
      • 따라서 이틀이 더 소요된다.
    • M이 N의 정수 부분보다 작거나 같은 경우
      • M을 만들기 위해서는, 1 ~ N 중 하나의 수를 더해야 한다.
      • 따라서 하루가 더 소요된다.

풀이

import sys

input = sys.stdin.readline
X, Y = map(int, input().split())

if Y - X <= 1:
    print(Y - X)
else:
    diff = int((Y - X) ** 0.5)
    if diff ** 2 == Y - X:
        print((diff * 2) - 1)
    else:
        other = (Y - X) - diff ** 2
        if other > diff:
            print((diff * 2) + 1)
        else:
            print(diff * 2)

통과!

읽어주셔서 감사합니다!