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

문제

---

코드

맞았습니다가 뜬 코드입니다. - 메모리 14220KB | 시간 124ms | 코드 길이 898B

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

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int m = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		
		if(m == d) {
			System.out.println(0);
			return;
		}
		
		double interval = d - m;
		
		double a = Math.sqrt(interval);
		
		if(a - (int)a > 0) {
			if(interval - Math.pow((int)a, 2) <= (int)a) {
				bw.write(Integer.toString((2 * (int)a - 1) + 1));
			}
			else {
				bw.write(Integer.toString((2 * (int)a - 1) + 2));
			}
		} else {
			bw.write(Integer.toString(2 * (int)a - 1));
			
		}
		
		bf.close();
		bw.close();
	}
}

이 문제 같은 경우에는 원숭이와 멍멍이의 키 차이가 얼마나 나느냐에 따른 정답(cm를 어떻게 더해야할지)이 어떻게 나올지를 먼저 써보고, 거기에서 규칙을 알아냈습니다.

규칙을 찾아보자면, 제곱수인 1, 4, 9, 16에서 찾아볼 수 있었습니다.

 

1은 1

4는 1+2+1

9는 1+2+3+2+1

16은 1+2+3+4+3+2+1

이런식으로요.

 

이 수들을 중심으로 밑의 수들 중 절반은 해당 수와 일자수가 같고, 절반은 1이 작습니다.

이런식으로요

double interval = d - m;
		
double a = Math.sqrt(interval);
		
		if(a - (int)a > 0) {
			if(interval - Math.pow((int)a, 2) <= (int)a) {
				bw.write(Integer.toString((2 * (int)a - 1) + 1));
			}
			else {
				bw.write(Integer.toString((2 * (int)a - 1) + 2));
			}
		} else {
			bw.write(Integer.toString(2 * (int)a - 1));
			
		}

그래서 첫번째 if문에서는 제곱수인지 먼저 체크를 했고,

제곱수가 아니라면 두번째 if문으로 절반 구역에 있는지 확인하여 1을 더하거나 2를 더했습니다. 저는 위에 있는 그림과 달리(9에서 5~8로 접근하는 방식) 4에서 5~8을 접근하는 식으로 가서 코드가 약간 다르긴 합니다.

 

Try1. 틀렸습니다가 뜬 코드입니다. - 코드 길이 839B

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

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int m = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		
		double interval = d - m;
		
		double a = Math.sqrt(interval);
		
		if(a - (int)a > 0) {
			if(interval - Math.pow((int)a, 2) <= (int)a) {
				bw.write(Integer.toString((2 * (int)a - 1) + 1));
			}
			else {
				bw.write(Integer.toString((2 * (int)a - 1) + 2));
			}
		} else {
			bw.write(Integer.toString(2 * (int)a - 1));
			
		}
		
		bf.close();
		bw.close();
	}
}

• 원숭이의 키와 멍멍이의 키가 같다는 조건을 쓰지 않아서 틀렸습니다.

---

후기

골드 수학문제라 약간 쫄았는데 무난하네요