[백준/Java]Q2292

백준 알고리즘 8단계 기본 수학1 2292번 문제입니다.

---

Q. 그림과 같이 육각형으로 이루어진 모형에서 숫자 N이 주어졌을때, 중앙 번호 1에서 N번까지 가는 횟수를 계산하는 프로그램을 작성하시오.

그림 출처 : https://www.acmicpc.net/problem/2292

[입력]
- 정수 N이 주어진다.

 

[조건]
- N(1 ≤ N ≤ 1000000000)
- 횟수는 시작과 끝을 포함한다.

 

풀이

그림을 분석해봤을 때 규칙을 한가지 찾을 수 있었다.
1 -> 5  : 2   1 -> 7  : 2
1 -> 8  : 3   1 -> 13 : 3   1 -> 10 : 3
1 -> 28 : 4   1 -> 20 : 4   1 -> 31 : 4
1 -> 40 : 5   1 -> 50 : 5
1 -> 69 : 6

 

N번까지 가는 횟수의 초기값은 2이고(물론 N이 1인 경우는 초기값이 1이어야 했다), Min값과 Max값을 구하면 그 안에 포함되는 경우에 한해 횟수가 동일하다는 것이다. 

즉, Min, Max값만 구할 수 있으면 문제를 풀 수 있었다.

Min값은 2를 기준으로 시작해서 8, 20, 38,... Max값은 7, 19, 37, 61,...

Min값은 6, 12, 18,... 6의 배수로 증가하고 Max값은 12, 18, 24,... 마찬가지로 6의 배수로 증가했다. 다만 Max값은 12(6x2)부터 증가되는 차이가 있었다.

 

소스

package com.baek.algo;

import java.util.Scanner;

public class Q2292 {

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

		int n = sc.nextInt();
		int cnt = 2;

		if(n == 1) {
			cnt = 1;
		} else {
			int i = 0;
			int min = 2;
			int max = 1;

			while(true) {
				min = min + (6 * i);
				max = max + (6 * (i + 1));

				if(n >= min && n <= max) {
					cnt = cnt + i;
					break;
				}

				i = i + 1;
			}
		}

		System.out.println(cnt);

		sc.close();
	}
}