알고리즘 문제 해결(PS)/[백준]

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

연구소장 J 2022. 3. 11. 10:47

문제

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

 

1669번: 멍멍이 쓰다듬기

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍

www.acmicpc.net

 

풀이

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

키차이 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);

	}

}
반응형