[백준 1229] 육각수 - C++

BOJ Link

https://www.acmicpc.net/problem/1229

 

풀이 과정

런타임 전의 전처리 + DP 문제이다.

 

알고리즘 문제의 분류로서 런타임 전의 전처리란,

솔루션 코드를 실행하기 이전에, 사전 작업을 통해 런타임 시 효율을 높히는

(시간복잡도를 줄이거나 메모리 효율을 높히는) 문제를 뜻한다.

 

이 문제에서, N <=100만 이다.

100만 이하의 N에 대해 모든 육각수를 구하는 과정을 전처리로 실행할 수 있다. 이는 곧 707개의 경우가 나온다.

 

이를 바탕으로 100만 길이의 dp[]를 갱신한다면,

O(707*100만) = 7억의 시간복잡도가 나온다. 문제의 제한이 2초기에, 나는 해당 코드가 통과하지 못할 것이라고 예상했다.

 

그래서 100만 길이의 배열 출력을 코드에 copy&paste하여 O(1)로 출력하는 방법을 생각했다. (전처리가 맞긴 하다..)

 

당연하게도 IDE가 먹통이되면서 결국 이전 코드를 제출해보기로 했다.

 

결과는, 1.4s가 나오면서 통과하였다.

 

제출 코드

#include <iostream>
#include <vector>

int MAX = 1000000;
std::vector<int> dp(MAX + 1, 6);
std::vector<int> vec;


int main() {

	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int num = 1;
	int weight = 5;

	int N;
	std::cin >> N;

	while (num < MAX) {
		vec.push_back(num);
		dp[num] = 1;
		num += weight;
		weight += 4;
	}

	for (int i = 0;i < N;i++) {
		for (int j = 0; j < vec.size(); j++) {
			if (i + vec[j] <= MAX)
				dp[i + vec[j]] = std::min(dp[i] + 1, dp[i + vec[j]]);
		}
	}

	std::cout << dp[N];
}