[2292] 벌집(C/C++)

🍃 문제

2292번: 벌집

 

 

🍃 해결 방법 

그림만 보고 압도되기 쉽지만... 계차수열 공식이 아직 머리에 남아있다면 빠르게 풀 수 있는 문제였다.

우선 1번 방에서 특정 방으로 이동하기 위해 몇개의 방을 지나야 하는지를 확인해보자.

1번 방부터 1번 방 : 1개

1번 방부터 2~7번 방 : 2개

1번 방부터 8~19번 방 : 3개

.

.

.

즉, 1개의 방만 거칠 수 있는 방 번호의 마지노선은 1번,

2개의 방만 거치면 되는 방 번호의 마지노선은 7번,

3개의 방만 거치면 되는 방 번호의 마지노선은 19번,

...

이 숫자들을 일렬로 나열해 보면 

위와 같은 규칙이 생긴다.

즉, an의 공차는 계차수열을 이루고 있으므로 계차수열 공식을 사용해서 an을 구한 뒤

입력받은 숫자가 a(n)과 a(n + 1)번째 사이에 있는지 확인해주면 된다.

bn은 6n이라는 등차수열을 이루고 있고,

이를 계차수열 공식에 넣으면

an = 1 + 3n(n - 1) 이 나온다!

n = 1 : an = 1

n = 2 : an = 7

이므로 입력받은 값이 an과 일치한다면 n을 출력하면 되고,

an보다는 크지만 a(n+1)보다는 작거나 같은 범위에 있다면 n+1을 출력하면 된다!

 

 

🍃 내 코드 

Ver.1(C)

//[2292] 벌집
// https://www.acmicpc.net/problem/2292

#include <stdio.h>

int main(void)
{
	int n;
	scanf("%d", &n);

	for (int i = 1;; i++) {
		if ((1 + 3 * i*(i - 1)) == n) {
            printf("%d\n", i);
			break;
		}
		else if ((1 + 3 * i*(i - 1)) < n && n <= (1 + 3 * (i + 1)*i)) {
			printf("%d\n", i + 1);
			break;
		}
	}
}

 

Ver.2(C++)

//[2292] 벌집
// https://www.acmicpc.net/problem/2292

#include <iostream>
using namespace std;

int main(void)
{
	int n;
	cin >> n;

	for (int i = 1;; i++) {
		if ((1 + 3 * i*(i - 1)) == n) {
			cout << i << endl;
			break;
		}
		else if ((1 + 3 * i*(i - 1)) < n && n <= (1 + 3 * (i + 1)*i)) {
			cout << i + 1 << endl;
			break;
		}
	}
}