백준 2292번 벌집(JAVA)

2292번: 벌집

풀이코드

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

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 target = Integer.parseInt(st.nextToken());
        int pass = 1; 	// 숫자 1로부터 지나온 방 수
        int max = 0;  // 탐색한 영역에 써있는 숫자의 최댓값
        
        while (max < target) { // 아직 타겟 숫자보다 찾은 숫자가 더 작으면
            pass += 1; // 지나온 방 수를 증가
            max += (6 * pass); // 숫자의 최대값 갱신
        }
        
        System.out.println(pass + 1); // 시작점을 포함하므로 1이 써져있는 방을 더해준다
    }
}

 

풀이과정

숫자 1을 기준으로 붙어있는 숫자들의 규칙을 찾는다.

지나쳐 온 방(pass)이 0일 때 탐색한 숫자 중 가장 큰 숫자는 1이다.

문제에 시작과 끝을 포함한다고 되어 있으니 만약 숫자 1을 찾는다면 지나온 방 수는 1이다. 

지나쳐 온 방(pass)이 2일 때 탐색한 숫자 중 가장 큰 숫자는 7이다.

지나쳐 온 방(pass)이 2일 때 탐색한 숫자 중 가장 큰 숫자는 19이다.

지나쳐 온 방(pass)이 3일 때 탐색한 숫자 중 가장 큰 숫자는 37이다.

지나쳐 온 방이 4일 때는 61, 5일 때는 91 ...

가장 큰 숫자를 나열해보면 1, 7, 19, 37, 61, 91 ... 각 숫자의 차이는 6, 12, 18, 24, 30 ... 지나쳐 온 방이 증가할수록 6의 배수가 더해지고 있는 것을 찾을 수 있다.

 

이를 코드로 나타내어 지나쳐 온 방에서 찾을 수 있는 가장 큰 수(max)를 찾아준다.

 

max += (6 * pass); // 숫자의 최대값 갱신

max는 지나쳐 온 방 수 * 6의 배수만큼 증가한다. 

 

while (max < target) { // 아직 타겟 숫자보다 찾은 최대값이 더 작으면
    pass += 1; // 지나온 방 수를 증가
    ...

만약 입력값이 max보다 작으면 현재는 찾을 수 없는 값이므로 max를 증가시켜준다.

 

만약 max가 더 크다면 찾을 수 있는 값이므로 반복문을 즉시 종료하고, 시작점을 포함하므로 지나온 방 수 + 1을 출력시켜야 한다.