[JAVA] BOJ(백준) - 멍멍이 쓰다듬기 - 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만큼 늘려야하는 조건이 있다.

 

이렇게 숫자를 가지고 노는 상황에서 조건을 주면 보통 규칙이 있다고 생각했고 수를 나열해 봤다.

키차이	키를 늘리고 줄이기
1	1
2	1 1
3	1 1 1
4	1 2 1
5	1 2 1 1
6	1 2 2 1
7	1 2 2 1 1
8	1 2 2 2 1
9	1 2 3 2 1

나열한 수를 보면 ^ 모양으로 수가 증가됐다가 줄어드는 수열을 볼수 있다.

이때 4와 9를 보면 가운데 수를 N이라 했을때 N^2이 된다는걸 알수 있다.

이를 활용해 아래와 같이 2가지 조건으로 나누고 문제를 풀 수 있다.

1. 키차이가 제곱수 일때
   키차이가 제곱수라면 가장 많이 크는 날짜는 N이라고 할 수 있다.
   예를 들어 키차이가 9라면 N=3이 된다.
   이때 키차이가 9일때 원숭이가 9cm를 크기 위해선 최소 5일이 필요하다.
   이를 구하기 위해 N을 이용해서 규칙을 찾아보면 "5일 = (N*2) -1" 로 표현할 수 있다.
   따라서 키차이가 제곱수 일때
   "최소일수 = (N*2) - 1" 이 된다.
   
   
2. 키차이가 제곱수가 아닐때
   키차이가 제곱수가 아니면 현재 키차이보다 작은 숫자중 가장큰 제곱수를 구해서 N을 구해서 활용하면 된다.
   예를 들어 키차이가 8일때 8에 근접한 가장큰 제곱수는 4이다. 따라서 N=2가 된다.
   이때 키차이 4cm는 1 2 1 방식으로 키가 크고 8cm는 1 2 2 2 1 방식으로 키가큰다.
   즉, 8cm일땐 4cm 일때 키크는 방식에서 중간에 2를 두번 추가면 되는 것이고,
   이말은 N보다 작은 자연수 1, 2 중에서 키차이를 최대한 줄일 수 있는 숫자를 선택해 나가면서
   최종적으로 키차이를 0으로 만들면 된다.

풀이 설명이 좀 힘들었는데

자세한 내용은 코드를 보고 이해해 보자.

 

---

풀이

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int monkey = Integer.parseInt(st.nextToken());
		int dog = Integer.parseInt(st.nextToken());
		int goal = dog - monkey;//원숭이가 늘릴키
		
		//늘릴키가 0,1,2일때는 바로 출력후 main함수 종료
		if(goal==0) {
			System.out.println(0);
			System.exit(0);
		}else if(goal==1) {
			System.out.println(1);
			System.exit(0);
		}else if(goal==2) {
			System.out.println(2);
			System.exit(0);
		}
		
		int num = (int) findNum(goal);//N 구하기 (N=num)
		int answer = (num*2)-1;//키를 같게하기 위한 가장 최소 일수
		if((num*num)==goal) {//만약 goal이 제곱수라면 answer 출력
			System.out.println(answer);
			System.exit(0);
		}
		
		//goal이 제곱수가 아니면 "최소일수 + 남은 키차이 줄이는 날짜"를 구해야한다. 
		System.out.println(dayCnt(num, goal, answer));
	}
	
	//N구하기
	public static double findNum(int goal) {
		double num = 2;//키차이가 3일때까지는 main에서 처리했기때문에
		//키차이가 4일때부터 생각하고 N을 구함.
		
		while(true) {
			//goal이 제곱수보다 크면 num 계속 증가
			if(Math.pow(num, 2) < goal) {
				num++;
			}
			//제곱수가 goal보다 커지는 순간 num하나 감소시키고 반복문 중단.
			else if(Math.pow(num, 2) > goal) {
				num--;
				break;
			}
			//제곱수와 goal이 같아지는 경우 중단.
			else break;
		}
		return num;
	}
	
	//남은 날짜 계산
	public static int dayCnt(int num, int goal, int answer) {
		int diff = goal - (num*num);//남은 키차이
		while(diff!=0) {
			if(num < diff) diff -= num;//남은 키차이가 num보다 크면 num을 빼줌
			else diff -= diff;//남은 키차이가 num보다 작으면 diff빼서 0으로 만들어줌
			answer++;//한번 실행할때 마다 answer 증가
		}
		return answer;
	}
}

---

마치며

나는 문제를 풀때 규칙을 찾기 힘들어서 생각보다 어려웠던 문제이다.

그리고 문제를 풀고나서도 말로 설명하기 애매해서 직접 구현해보며 이해하는게 가장 좋은 방법이라 생각한다.