[코딩테스트] 멍멍이 쓰다듬기

문제

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

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

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

입력

첫째 줄에 원숭이의 키 X와 멍멍이의 키 Y가 주어진다. X, Y는 0 ≤ X ≤ Y < 231을 만족하는 정수이다.

출력

첫째 줄에 원숭이가 멍멍이의 키와 같아지게 되는 최소의 일수를 출력한다.

예제 입력 1

45 49

예제 출력 1

3

예제 입력 2

45 50

예제 출력 2

4

생각

• diff = 원숭이의 키와 멍멍이의 키 차이
• diff가 1~3인 경우, 첫날과 마지막날의 키 증가량은 1cm이므로 diff에 해당하는 값이 최소 일수.
• diff가 4 이상인 경우, 키 증가량은 매일 1cm씩 증가할 수 있으므로 cur을 현재 키 증가량의 기준점으로 두고 다음과 같이 계산:
  1. 첫 2일 동안 키 증가량은 각각 1cm. 따라서 minDays를 2로 설정하고, diff에서 2를 빼서 초기화.
  2. cur을 1로 설정하고, 반복문을 시작
  3. diff가 cur + 1 이하인 경우:
     minDays에 1을 추가, 반복 종료
  4. diff가 (cur + 1) * 2보다 작은 경우:
     minDays에 2를 추가, 반복 종료
  5. diff가 (cur + 1) * 2 이상인 경우:
     cur을 1씩 증가 (키 증가량을 증가시킴).
     minDays에 2를 추가하고, diff에서 해당 키 증가량을 빼는 방식으로 반복.
     

코드

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

public class PettingPuppy {

    public int getMinNumberOfDays(int monkey, int puppy) {

        int diff = puppy - monkey;
        if (diff <= 3)
            return diff;

        int minDays = 2;
        diff -= 2;
        int cur = 1;

        while (diff > 0) {
            if (diff <= (cur + 1) * 2) {
                minDays++;
                if (diff > cur + 1) {
                    minDays++;
                }
                break;
            } else {
                diff = diff - (cur + 1) * 2;
                minDays += 2;
                cur++;
            }
        }

        return minDays;
    }

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

        String[] line = br.readLine().split(" ");
        System.out.println(T.getMinNumberOfDays(Integer.parseInt(line[0]), Integer.parseInt(line[1])));
    }

}

추가

• 다른 사람의 풀이들을 살펴보니 대부분 제곱수(ex 4, 9, 16...)를 사용해서 문제를 풀었다: 참조한 다른 사람의 블로그
• 제곱수보다 1 커졌을 때 항상 minDays가 1일 이용한다는 규칙을 사용해서 diff보다 작거나 같은 최대 제곱수를 찾고, 그 이후를 계산하는 방식이다. 시간 복잡도를 줄일 수 있다는 점에서 좋은 방식이라고 생각하였다!

---

문제 출처