본문 바로가기
[개발] 알고리즘

백준 2292 - 벌집 자바로 풀기

by Devsong26 2017. 11. 20.

- 문제 출처: https://www.acmicpc.net/problem/2292

 

- 해결 방법

입력되는 숫자가 N이라고 할 때, 

N=1일 경우, 1 -> 1 로 이동하는 것은 1개의 방을 지납니다.

1<N<=7 일 경우, 2개의 방을 지납니다. 

7<N<=19일 경우, 3개의 방을 지납니다. 

19<N<=37일 경우, 4개의 방을 지납니다. 

37<N<=61일 경우, 5개의 방을 지납니다. 

...

 

즉, 1, 7, 19, 37, 61, ... 수열을 이용하여 문제를 해결하면 됩니다. 

1 = 1,

7 = 1 + 6, 

19 = 1 + 6 + 12,

37 = 1 + 6 + 12 + 18,

...

 

이 수열의 일반항은 3n^2-3n+1(단, n>=2)입니다.

코드상에서는 변수를 1로 초기화 한 다음에 그 값의 6의 배수를 곱한 값을 변수에 더해주어 입력값 N과 비교하면 됩니다. 

 

코드는 아래와 같습니다. 

import java.io.BufferedReader;

import java.io.InputStreamReader;

 

public class Main{

public static void main(String[] args) throws Exception{

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int n = Integer.parseInt(br.readLine().trim());

br.close();

int sum = 1, i = 0;

for(; sum<n; i++){

sum+=6*(i+1);

}

System.out.println(i+1);

}

}

 

i+1은 최소한의 방을 지나는 개수를 나타냅니다. 

i를 0부터 시작하는 이유는 N=1일 때를 포함한 모든 경우를 나타내기 위함입니다. 

 

이상으로 포스팅을 마칩니다.