BaekJoon 2292 벌집

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

소스결과 2376 KB / 0 ms

출처 BackJoon, ACM-ICPC Seoul National Internet Competition 2004 B번

언어 C++ 17

분류 다이나믹 프로그래밍, 수학

 

설명

입력받은 숫자 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;
}