[백준] 1669번 멍멍이 쓰다듬기 (자바 풀이)

문제

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

1669번: 멍멍이 쓰다듬기

 

풀이

나는 수학 문제가 너무 어렵다. 이 문제는 수열 문제로 생각을 잘해야 풀 수 있다.

키차이	Day 1	Day 2	Day 3	Day 4	Day 5
1cm	1
2cm	1	1
3cm	1	1	1
4cm	1	2	1
5cm	1	2	1	1
6cm	1	2	2	1
7cm	1	2	2	1	1
8cm	1	2	2	2	1
9cm	1	2	3	2	1

키차이에 따른 키 크는 과정이다. 잘보면 4cm, 9cm 는 1,2,1  |  1,2,3,2,1 와 같이 ^모양(증가하다가 감소) 수열을 나타내는 것을 확인 할 수 있다.

 

따라서 2^2, 3^2, 4^2...n^2 처럼 제곱수는 2*n-1 만큼 키크는 과정이 걸리는 것을 확인할 수 있다.

 

그렇다면 제곱수가 아닌 키차이는 어떻게 계산할 까? 

 

예를 들어 키차이가 7cm인 경우를 살펴보자. 이경우 키차이가 4cm일 때 수열인 1,2,1 에 3cm를 더해서 1,2,(2),(1),1 이렇게 5일이 걸리는 것을 알 수 있다. 이때 사용할 수 있는 가장 큰 수를 집어넣어야 하는데, 키차이가 4cm에서 넣을 수 있는 가장 큰 수는 4의 제곱근인 2다. 따라서 2를 넣고 남은 1을 넣으면 된다.

 

코드

import java.io.*;
import java.util.*;

public class Baekjoon_1669 {
	static int X,Y;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		X = sc.nextInt();
		Y = sc.nextInt();
		
		int diff = Y-X;
		long n = 0;
		
		if(X==Y) {
			System.out.println(0);
			return;
		}
		
		while(n*n < diff) {
			n++;
		}
		
		if(n*n != diff) {
			n--;
		}
		
		long ans = 2*n-1;
		diff -= n*n;
		
		while(diff > 0) {
			diff -= Math.min(n, diff);
			ans++;
		}
		
		System.out.println(ans);

	}

}