[BackJoon]2292번 스트림으로 풀기

문제

 

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 

그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 

숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 

몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 

예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

 

입력

 

첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

 

출력

 

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

 

풀이

 

문제를 한 마디로 축약하면 <주어진 방이 몇 번째 껍질에 포함되는지 구하시오>라고 할 수 있다.

 

해서 규칙을 찾으면 첫 번째 껍질은 1개, 두 번째는 6개, 세 번째는 12개, 그 다음은 18개...로 방의 개수가 증가한다.

 

이를 모두 더한 값이 n번째 껍질까지의 총 방의 개수가 되므로(1, 7, 19, 37...)

 

방의 총 개수는 첫째항이 6이면서 공차가 6인 등차수열을 계차수열로 갖는, 첫째항 1인 수열이라고 할 수 있다.

 

말이 좀 꼬였는데.. 어쨌거나 일반항을 구해보면 첫째항이 a이고 공차가 d인 등차수열의 일반항은

 

$$a_{n}=a + (n-1)d$$

 

가 되며, 이 문제의 경우 매우 단순하게

 

$$a_{n}=6n$$

 

이 된다. 이어서 중간과정을 생략하고 n번째 항까지 합을 구하면 아래와 같고,

 

$$ S_{n} = 3(n^{2} + n) $$

 

따라서 우리에게 필요한 방의 총 개수, 계차수열의 일반항은

 

$$b_{n} = 1 + 3(n^{2} + n)$$

 

이 된다는 것을 알 수 있으며, 이제 코드로 옮기기만 하면 된다.

 

시작하기 전에, 입력값이 10억까지 주어진다고 하길래 스트림을 사용하고 싶어서 꼼수를 부렸다.

 

대략 몇 번째 껍질이 되어야 방의 개수가 10억 개를 돌파할까? 주어진 식을 가지고 계산하니 대략 31623이 나와

 

IntStream으로 1에서 31623까지 인위적으로 설정해 돌았다.

 

전체 방의 개수를 다 돌면서 주어진 방을 넘는 모든 껍질을 필터링해서 최솟값을 구하는 식의 계산이다.

 

효율성은 매우 떨어져 보이긴 하지만.. 일단 통과는 했다.

import java.util.Scanner;
import java.util.stream.IntStream;

public class Prob2292Stream {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int result = IntStream.rangeClosed(1, 31623)
                .filter(x -> 1 + 3 * (Math.pow(x, 2) - x) >= n)
                .min().getAsInt();

        System.out.println(result);
    }
}