[Java] 백준 1669번 - 멍멍이 쓰다듬기

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

1669번: 멍멍이 쓰다듬기

문제

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

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

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

입력

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

출력

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

 

---

접근 방법

이 문제는 규칙을 잘 찾아야하는 문제이다. 문제에서 주어진 조건을 봐보면 키를 1cm 차이가 나게 조절을 해야하는데, 이 때 첫째 날과 마지막 날은 무조건 1cm가 되어야 한다. 이 점을 유의깊게 봐보자.

 

우리는 최소의 일수를 구해야 하기 때문에 첫째 날 키 조절 양을 1cm 로 시작을 해서 2, 3, 4,,, 로 키를 키워나가야 하지만

마지막 날의 키 조절 양도 1cm로 끝나야하기 때문에

어느 정도 고점 x에 도달한 뒤에는 x-1, x-2, x-3,,, 1 과 같이 키의 양을 줄여나갸야 하는 것이다. 

 

그렇다면  그 고점을 어떻게 찾아야할까? 

규칙이 보이지 않을 때에는 먼저 나열을 쭉 해보고 그 안에서 규칙을 찾아보는것도 좋은 방법이다. 

 

키 차이 (Y-X) 를 sub이라고 하자. 멍멍이와 원숭이의 키가 같아지기 위한 최소 일수를 찾아보자. 

   * 괄호 안의 수는 각 날에 조절한 키의 양이다.)

sub = 1 일 때 : 1일 (1)

sub = 2일 때 : 2일 (1, 1)

sub = 3일 때 : 3일 (1, 1, 1)

sub = 4일 때 : 3일 (1, 2, 1)

sub = 5일 때 : 4일 (1, 2, 1, 1)

sub = 6일 때 : 4일 (1, 2, 2, 1)

 

sub = 7일 때 : 5일 (1, 2, 2, 1, 1)

sub = 8일 때 : 5일 (1, 2, 2, 2, 1)

sub = 9일 때 : 5일 (1, 2, 3, 2, 1)

sub = 10일 때 : 6일 (1, 2, 3, 2, 1, 1)

sub = 11일 때 : 6일 (1, 2, 3, 2, 2, 1)

sub = 12일 때 : 6일 (1, 2, 3, 3, 2, 1)

sub = 13일 때 : 7일 (1, 2, 3, 3, 2, 1, 1)

sub = 14일 때 : 7일 (1, 2, 3, 3, 2, 2, 1)

sub = 15일 때 : 7일 (1, 2, 3, 3, 3, 2, 1)

sub = 16일 때 : 7일 (1, 2, 3, 4, 3, 2, 1)

sub = 17일 때 : 8일 (1, 2, 3, 4, 3, 2, 1, 1)

 

제곱수를 보면 sub = N^2 라고 했을 때 고점이 N 인것을 확인할 수 있고, 필요한 최소 일수는 N^2 - 1 인 것을 확인할 수 있다. 
그렇다면 제곱수가 아닌 수는 어떤 규칙이 있을까?

예를 들어 sub = 13일 때를 보자. 13보다 작은 제곱수인 9(1, 2, 3, 2, 1) 을 제외하면 (1, 2, 3, 3, 2, 1, 1) 중 (3, 1)이 남는데

이는 루트 9보다 작은 수 중 적당히 끼워 넣은 것이다. 

 

즉,

1) 키 차이보다 작은 최대 제곱수 N^2 를 찾고

2) 키 차이에서 최대 제곱수를 뺀 나머지를 구한 다음

3) 나머지가 N이하의 수들로 어떻게 구성되어있는지 찾으면 되는 것이다. (문제에서 최소 일수를 찾는 것이 목표이기 때문에 이때 가장 큰 수인 N부터 검사하도록 한다. )

 

이를 코드로 나타내면 아래와 같다.

 

*주의 ) N과 ans를 long형으로 선언해야한다. (오버플로우 방지 (?) )

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();
        int y = sc.nextInt();
        int sub = y - x;
        
        if(sub == 0){				// 예외처리 : 처음부터 키가 같을 때
            System.out.println(0);
            return;
        }

        long N = 1;				//long 형으로 선언해야한다.
        long ans = 0;

        while(N*N <= sub){ 			//키차이보다 작은 최대 제곱수를 찾는다.
            N++;
        }
        N-=1;					//N++된 상태로 while문을 빠져나오기 때문에 -1 해준다.
        ans = 2*N - 1;				//answer 초기 값 설정 

        sub -= N*N;				//제곱수만큼 빼고 남은 키로 while 문을 돈다.
        while(sub > 0){

            for(long i = N; 1<=i; i--){		//N부터 시작해서
                if(i<=sub){					//i가 sub보다 작으면 
                    ans+=1;
                    sub -= i;				//sub에서 i를 뺀다.
                    break;
                }
                else continue;				
            }
        }
        System.out.println(ans);
    }

}