[BOJ] 2292 벌집

Link https://www.acmicpc.net/problem/2292

Note

입력받은 숫자 n이 1을 포함하여 몇번째 외곽에 존재 하는지 푸는 문제

친구가 어떻게 풀지 물어봐서 풀어본 문제
이번 문제는 푸는 방법이 여럿 존재한다. 점화식이 너무 선명하다
1을 기준으로 오른쪽 대각선의 값이 6 * i 를 더한 값이 계속 반복되기 때문
반복문을 통해서 푸는게 가장 짧은 코드이지만 지금은 DP에 대해서 계속 공부하고 있는 중이기에 DP로 풀었다.

알고리즘

1. 외곽의 최대 값을 입력할 배열 dp를 생성 및 초기화를 한다.
   1 - 1. 0번 인덱스를 1로 초기화 한다.
   1 - 2. n번 인덱스를 dp[n-1] + ( 6 * n ) 의 계산결과를 대입한다.
2. 결과를 원하는 값 x를 반복문을 통해 x의 값을 계산한다.

소스코드

#include <iostream>

using namespace std;

const int MAX = 1000000000;

int dp[100000];

int main()
{
	int n;
	int counter = 0;

	cin >> n;

	// dp init
	dp[0] = 1;
	for (int i = 1; dp[i -1] < MAX; i++)
		dp[i] = dp[i - 1] + (6 * i);

	for (int i = 0; i < 5; i++)
		cout << dp[i] << ' ';
	cout << endl;

	while (n > dp[counter])
		counter++;

	cout << counter + 1;

	return 0;
}

2019-01-13 11:00:00에 Tistory에서 작성되었습니다.