백준 - 1669번(멍멍이 쓰다듬기)

문제 출처: https://www.acmicpc.net/problem/1669

문제

• 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍멍이보다 키가 작기 때문에 멍멍이를 쓰다듬어줄 수 없다. 원숭이가 멍멍이를 쓰다듬으려면 둘의 키가 같아야 하기 때문이다.

• 그래서 원숭이는 그 날부터 자신의 키를 조절하기로 마음먹었다. 원숭이는 초능력자이기 때문에 마음대로 키를 늘릴 수 있다. 하지만 안타깝게도 사람이 아니라 동물이기 때문에 하루에 늘릴 수 있는 키의 양을 1cm밖에 조절할 수 없다. 예를 들어 오늘 키를 5cm 만큼 늘렸다면, 내일은 키를 4cm, 5cm, 6cm 중 하나만큼 키를 늘릴 수 있다는 뜻이다. 늘릴 수 있는 키의 양은 음수가 될 수 없다. 그리고 첫째 날과 마지막 날에는 무조건 1cm 만큼 늘릴 수 있다.

• 현재 원숭이와 멍멍이의 키가 주어졌을 때, 원숭이가 매일 키를 늘려서 멍멍이와 키가 같아지는 최소의 일수를 구하는 프로그램을 작성하시오.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int X = Integer.parseInt(tokenizer.nextToken());    // 원숭이
        int Y = Integer.parseInt(tokenizer.nextToken());    // 멍멍이

        int target = Math.abs(X - Y);

        if (target < 3) {
            System.out.println(target);
            return;
        }

        int day = 2;
        int height = 1;
        target -= 2;

        while (target > 0) {
            if (target <= (height + 1) * 2) {
                // 이제 끝
                if (target <= (height + 1)) {
                    day++;
                } else {
                    day += 2;
                }
                break;
            } else {
                target -= (height + 1) * 2;
                day += 2;
                height++;
            }
        }

        System.out.println(day);
    }

}

• 수학 문제라서 잔뜩 겁먹고 들어가서 '이게 과연 풀릴까?' 하며 채점했는데 얼떨결에 맞아서 되게 당황했던 문제다.
• 다른 사람들의 풀이를 보니 이해가 잘 안됐다.
• 아주 간단한 방법으로 풀이를 하였다. 우선, 처음과 끝 날은 1cm로 고정이므로 이 둘을 합친 2cm 까지는 값을 구하는데 특별한 로직이 없으므로 바로 값을 출력하고 return; 하였다.
• 값이 3 이상일 경우 로직 처리가 들어간다. 우선 처음에 양 끝 날의 합인 2cm를 빼준다. 그 다음, 남은 길이가 현재 키의 +1 한 값의 2배보다 큰지 확인한다. 키가 늘어날 때도 그렇고 줄어들 때도 그렇고 최대 변화 폭이 1cm이므로 양쪽에서 같이 움직이도록 처리하였다.
• 만약 남은 길이가 (현재 키 + 1)의 2배보다 클 경우, 키에서 이 (현재 키 + 1) * 2 값을 빼주고 양쪽에서 진행하므로 날짜를 2 더한 뒤, 키를 1 증가시키고 로직을 반복한다.
• 만약 남은 길이가 (현재 키 + 1)의 2배 이하일 경우, 이제 원숭이는 하루나 이틀 조절하면 키가 같아질 수 있다.
• 만약, (현재 키 + 1) 초과인 경우 이틀이 필요하므로 2를 더하고 끝내고, 이하인 경우 하루만 하면 되므로 1을 더하고 끝낸다.