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

문제

 

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

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

숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를

계산하는 프로그램을 작성하시오.

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

 

입력

 

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

 

출력

 

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

 

풀이

 

지나는 방의 개수를 구하기 위해 해당 껍질의 최댓값을 나열하면 1, 7, 19, 37.. 순으로 증가한다. 

 

즉 첫 항이 1이고 계차수열이 6(n - 1)인 수열의 일반항을 구하는 문제이다.

 

스트림을 사용하기 위해 주어진 입력값에서 조건에 맞는 리스트를 필터링 한 뒤에

 

그중 최솟값을 출력하려고 한다.

 

등차수열의 합을 이용해 간단하게 일반항을 구해보면

 

a_x = 3(x² - x) + 1

 

이 되며, 문제에서 주어진 입력의 최댓값, 즉 a_x가 1,000,000,000이기 때문에

 

a_x = 3(x² - x) + 1 = 1000000000

 

을 만족하는 x 값, 즉

 

x = 31623

 

까지만 순회하면 된다.

 

정리하면 스트림을 이용해 1부터 31623까지 순회하며 주어진 N값을 만족하는 아래와 같은 x를

 

3(x² - x) + 1 ≥ N

 

필터링한 뒤에

 

그중 최솟값을 출력하면 된다.

 

• 1 → 1
• 2 ~ 7 → 2
• 8 ~ 19 → 3
• 20 ~ 37 → 4

와 같이 출력하면 되기 때문이다.

 

코드를 보자.

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(); // N값 입력

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

        System.out.println(result);
    }
}