2292번. 벌집

 

아이디어

입력값 N에 따른 최소 방 갯수
0 < N <= 1 : 1
1 < N <= 7 : 2
7 < N <= 19 : 3
19 < N <= 20 : 4
...

 

여기서 규칙성을 찾아보면 다음과 같습니다.

입력값 N에 따른 최소 방 갯수
0 < N <= 6*0 + 1 : 1
6*0 + 1 < N <= 6*1 + 6*0 + 1 : 2
6*1 + 6*0 + 1 < N <= 6*2 + 6*1 + 6*0 + 1 : 3
6*2 + 6*1 + 6*0 + 1 < N <= 6*3 + 6*2 + 6*1 + 6*0 + 1 : 4
...

 

1 ~ n까지의 합은 n*(n+1)/2 로 표현할 수 있으니 정답을 k라고 할 때 수식을 정리해보면 다음과 같습니다.

 

 

3*(k-2)*(k-1) + 1 < N <= 3*(k-1)*k + 1

x = k-2 라고 하고 좌변의 조건을 통해 반복문을 돌리면

3*(x)*(x+1) + 1 < N 을 만족하는 동안 x를 하나씩 키워가다가 해당 조건을 만족하지 않을 때 탈출하게 하고 이를 통해 정답까지 얻어낼 수 있습니다.

 

풀이코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        int x = 0;
        if (N != 1) {
            while (3*(x)*(x+1) + 1 < N) {
                x++;
            }
        }

        System.out.println(x+1);
    }
}

        // x + 1을 출력하는 이유
        // k : 정답, x = k - 2
        // 우리가 구하려고 하는 값은 3*(x)*(x+1) + 1 < N 을 만족하는 x의 최대값
        // while 문을 탈출했을 때 x는 그 최대값보다 1이 큰 상황이므로 x + 2 가 아닌 x + 1로 출력