[백준] 1669번. 멍멍이 쓰다듬기(JAVA)

문제

https://www.acmicpc.net/problem/1669

---

풀이(15분)

import java.io.*;

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

        String[] tokens = br.readLine().split(" ");
        long X = Long.parseLong(tokens[0]);
        long Y = Long.parseLong(tokens[1]);

        long sub = Y - X;

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

        long pow = 0;
        while (pow * pow <= sub) {
            pow++;
        }
        pow--; // pow^2 <= sub 인 최대 pow 값

        long pows = pow * pow;
        long answer;

        if (sub == pows) {
            answer = 2 * pow - 1;
        } else if (sub <= pows + pow) {
            answer = 2 * pow;
        } else {
            answer = 2 * pow + 1;
        }

        System.out.println(answer);
    }
}

---

문제 풀이 전략

 

기본 아이디어

• 길이가 1이라면 1일이 최소일 것이다.
• 화살표의 왼쪽을 Y - X, 오른쪽을 각 일마다의 이동 거리 값(다양할 수 있다)으로 생각해 보자.

---

예시 분석

• 2 -> 1 1
• 3 -> 1 1 1
• 4 -> 1 2 1
  → 1 2 1은 중요한 값이다.
  → 중간이 1이 아닌 2로 올라갔다 내려가는 배열이 완성됐기 때문이다.
• 5 -> 1 2 1 1
  → 3을 쓸 수 없기 때문이다.
• 6 -> 1 2 2 1
  → 3을 쓸 수 없기 때문이다.
• 7 -> 1 2 2 1 1
  → 3을 쓸 수 없기 때문이다.
• 8 -> 1 2 2 2 1
  → 3을 쓸 수 없기 때문이다.
• 9 -> 1 2 3 2 1
  → 이제야 3을 쓸 수 있는 조건이 됐다.

---

핵심 패턴

• 예시들을 보면, "중간값이 올라갔다 내려가는 구조"가 완성되는 최소 조건은
  n^2일 때이다.
• 이를 이용하여 최소 일수를 계산할 수 있다.