[백준] 1로 만들기

문제 링크

 

풀이

실제로는 10분도 안 돼서 풀었는데, 사소한 실수 하나 사소하지 않은 결과를 만들어 해결까지 거의 30분을 넘게 썼습니다. 처음부터 실수하지 않게 주의하는 것이 중요한 것 같습니다. vs에서는 정적 배열을 백만 개 만들면 경고를 주면서, 프로그램 실행이 되지 않습니다. 동적 배열을 직접 만들거나 벡터를 쓰면 됩니다. 백준에서는 편의성을 위해 스택 공간을 많이 잡아둔 것 같습니다. 정적 배열 백만 개를 만들어도 괜찮네요.

 

이 문제는 전형적인 DP 문제입니다. d[i]는 i를 1로 만들기 위한 최소 연산 횟수입니다. d[i]는 d[i-1], d[i/2], d[i/3] 중에서 가장 작은 값에 1을 더해주면 되는데, 문제에 나와 있듯이 i가 2의 배수면 2로 나누고, 3의 배수면 3으로 나누는 것에 관한 처리를 넣어야 합니다. iostream을 안 쓰는 이유는 성능을 조금이라도 올리기 위해서입니다. 인클루드도 최소화하는 게 좋기 때문에 min이나 max 같은 간단한 함수는 직접 구현했습니다.

 

코드

#include <cstdio>
int min(int a, int b)
{
	return a < b ? a : b;
}
int main()
{
	int n;
	scanf("%d", &n);
	int d[1000001] = {};
	d[2] = d[3] = 1;
	for (int i = 4; i <= n; ++i)
	{
		d[i] = d[i - 1] + 1;
		if (0 == i % 3)
			d[i] = min(d[i], d[i / 3] + 1);
		if (0 == i % 2)
			d[i] = min(d[i], d[i / 2] + 1);
	}
	printf("%d\n, d[n]);
}