1463

1 만들기

 

 

백준 문제 중에 제일 많이 틀린 것 같다 .. 이 문제를 이렇게 많이 푼 사람은 나밖에 없을 것,,,

 

시간초과 문제 때문에 배열에 저장을 해줘야겠다는 생각까지는 했는데,,

처음에 그냥 int 일차원 배열을 쓰는데 크기가 10^6이라 배열이 그 크기까지 클 수 없었나봄. 그래서 vector배열을 써줬다

2의 배수이면서 3의 배수인 경우를 생각을 못해서 4% 에서 틀림 떠서 우울했다..

 

또 1일때 당연히 1일 줄 알았는데 0이더라. 당연함 제목부터가 1만들기임.

 

이 문제 푼사람 정말 많던데 나는 어려웠다 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> graph(1000001,0);

	graph[1] = 1;
	graph[2] = 1;
	graph[3] = 1;

	for (int i = 4;i < n+1;i++) {
		int flag = 0;
		if (i % 6 == 0) {
			flag = (graph[i / 2] < graph[i / 3]) ? 2 : 3;
		}
		else if (i % 2 == 0) {
			flag = 2;
		}
		else if (i % 3 == 0) {
			flag = 3;
		}


		if(flag==0) {
			graph[i] = 1 + graph[i - 1];
		}
		else {
			graph[i] = min(1 + graph[i - 1], 1 + graph[i / flag]);
		}
	

	}

	cout << graph[n];
	return 0;
}