[백준] 1669. 멍멍이 쓰다듬기

문제 링크

[백준] 1669. 멍멍이 쓰다듬기

풀이 과정

수학 문제입니다. 아래 그림을 보며 설명하겠습니다.

위 표에서 볼 수 있듯, 1cm부터 각각의 키차이에 대해 필요한 최소 일자를 작성해볼 수 있습니다.

• 예를 들어 원숭이와 멍멍이의 키차이가 4cm라면, 1일차부터 순서대로 [1, 2, 1] 의 순서로 키를 증가시키면 3일만에 원숭이와 멍멍이의 키가 같게 됩니다.
• 또, 둘의 키 차이가 9cm라면 [1, 2, 3, 2, 1] 의 순서로 5일만에, 키 차이가 16cm라면 [1, 2, 3, 4, 3, 2, 1] 로 증가시켜 7일만에 같게 만들 수 있습니다.

즉, 둘의 키 차이가 $N^2$이라면, 둘을 같게 하기 위해선 $2*N-1$일만큼이 필요하다는 것을 알 수 있습니다.

키 차이가 제곱수인 경우는 위와 같이 필요한 최소 일자를 바로 구할 수 있지만, 그렇지 않은 경우는 다음과 같이 생각해볼 수 있습니다.

1. 제곱수는 증가한 후 감소하는 ^ 모양을 띠는 수열을 형성한다.
2. 문제에서 주어진 둘의 키 차이보다 작은 최대 제곱수를 구해, 그 수가 만드는 ^ 모양의 수열을 이용하자.
   • 예를 들어, 키 차이가 6cm라면, 6보다 작은 최대 제곱수인 4cm가 만드는 수열 [1, 2, 1]에 2를 추가해 [1, 2, (2), 1]로 만들 수 있다.
   • 예를 들어, 키 차이가 10cm라면, 10보다 작은 최대 제곱수인 9cm가 만드는 수열 [1, 2, 3, 2, 1]에 1을 추가해 [1, 2, 3, 2, (1), 1]로 만들 수 있다.

위에서 설명한 추가해야되는 수는 다음과 같이 구할 수 있습니다. 위 그림에서, 7cm(파란색)의 키 차이를 **동일하게 하려면, 7보다 작은 최대 제곱수인 **4cm(빨간색)를 이용해야 한다는 것을 알 수 있습니다. 그 둘의 차이는 3cm가 되고, 따라서 이틀동안 2cm와 1cm를 각각 추가해 주어야 합니다.

4cm가 만드는 수열은 [1, 2, 1]로, 수열 내 최대 값은 $\sqrt{4}=2$가 되고, 남은 3cm만큼의 차이를 좁히기 위해서는 2이하의 수만 이용할 수 있습니다. 하루에 사용할 수 있는 가장 큰 값 순서대로 남은 키 차이를 좁혀갈 수 있습니다.

따라서, 남은 3cm를 수열 내 사용할 수 있는 가장 큰 수 2로 채우고, 그 후에 남은 1cm를 수열 내 사용할 수 있는 1로 채우면 키 차이가 0이 되며 종료됩니다.

int X = sc.nextInt();
int Y = sc.nextInt();
int diff = Y - X;
long n = 0;

풀이에 사용한 변수입니다.

• 원숭이 키를 X, 멍멍이 키를 Y, 둘의 차이를 diff로 설정합니다.
• n은 최소 제곱값의 제곱근을 의미합니다. 아래 코드에서 $n^2$을 구하는 코드가 있으므로, long 타입으로 선언해 오버플로우를 방지합니다.

if (diff == 0) {
    System.out.println(0);
    return;
}

diff가 0이면, 위에서 살펴본 규칙을 적용할 수 없는 예외 상황이므로, 0을 출력 후 종료합니다.

while (n * n < diff) n++;

n = (n * n == diff) ? n : n - 1;

제곱근 값 n을 증가시키며, diff 보다 작은 최대 제곱수를 구합니다. while문을 종료한 뒤, n이 올바른 값을 갖도록 조정해줍니다.

long answer = 2 * n - 1;
diff -= n * n;

n을 이용해 최소한의 필요한 일수를 구한 뒤 answer에 저장해둡니다. 이후, diff 에서 $n^2$을 빼, 남은 키 차이 값으로 갱신합니다.

while (diff > 0) {
    diff -= Math.min(n, diff);
    answer++;
}

이제 diff 가 0이 될 때 까지 아래 과정을 반복합니다.

• diff 값을 수열이 만드는 최대 값 n과, 필요한 키 차이 값 diff 중 작은 값을 빼주는 작업을 통해 diff 값을 갱신해줍니다.
• answer를 증가시켜, 필요한 일수를 1씩 늘려줍니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt();
        int Y = sc.nextInt();
        int diff = Y - X;
        long n = 0;

        if (diff == 0) {
            System.out.println(0);
            return;
        }

        while (n * n < diff) n++;

        n = (n * n == diff) ? n : n - 1;
        long answer = 2 * n - 1;
        diff -= n * n;

        while (diff > 0) {
            diff -= Math.min(n, diff);
            answer++;
        }

        System.out.println(answer);
    }
}