[Java] 백준 2292번

Input-1
13
Output-1
3

문제 풀이

이 문제는 특정 로직을 잘 파악하여 패턴을 나열하며 풀어야 한다.

먼저 1부터 N까지의 최소 루트를 구하는 것이니 N이 1일 경우엔 1이면 된다.
N이 2이상일 경우에는 아래와 같은 패턴을 유추해볼 수 있다.

N의 범위	벌집의 개수	최소 루트
2 ~ 7	6	2
8 ~ 19	12	3
20 ~ 37	18	4
38 ~ 61	24	5

위 패턴을 통해 벌집의 개수인 6의 배수 및 N의 범위별로 최소루트가 증가함을 알 수 있다.

벌집의 개수인 특정 6의 배수보다 N보다 작을 때 최소루트를 증가시키고 아니라면 반복문을 탈출하면 된다.
코드로 한번 작성해보자.

반복문 내에서 N이 특정 6의 배수보다 작을 때 range라는 변수를 1로 초기화한 후
N보다 작으면 6의 배수에 +1만큼 더하여 검증할 수 있도록 한다.

int n = Integer.parseInt(br.readLine());
int cnt = 1; // 최소 루트
int range = 1; // n의 범위
if(n > 1) {
    while(n > range) { // n의 값과 가장 근소한 6의 배수일 경우
        range = range + 6*cnt; // 6의 배수별로 순회
        cnt++; // 6의 배수마다 카운트 증가
    }
}
bw.write(cnt + "\n"); // 최소 루트 출력

range를 1로 초기화한 이유는?
실제로 N의 범위는 2~7, 8~19, 20~37 일때 순서대로 2, 3, 4의 최소루트를 가진다. 예를들어 N이 7이라 해보자.
range는 1+6*1 = 7이고, 최소루트(cnt)는 2가 된다.

그리고 range가 7이어 N과 같기에 반복문을 탈출할 수 있게된다.
그런데 만약 range가 0이라면 7이나 19, 37, 61 등의 경우에 한바퀴를 더 돌게 되어 최소루트가 3이되므로 +1을 하여 초기화를 해준 것이다.

작성코드

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        int cnt = 1; 
        int range = 1;

        if(n > 1) {
            while(n > range) {
                range += 6*cnt;
                cnt++;
            }
        }
        bw.write(cnt + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

회고

• 문제의 패턴을 이해하고 보니 알고리즘 자체는 쉬운편이었는데, 문제의 내용을 이해를 전혀 못해 시간이 많이 소요되었다.
  한 문제에 너무 많은 시간을 투자한 것이 아쉽지만 꼭 이 문제의 패턴이나 로직의 느낌을 잘 알아두어야 겠다.