[1463] 1로 만들기 - C 풀이

알고리즘 설계 기법

• DP

처음에는 그리디로 푸는 줄 알고 그냥 연산 방법 1, 2, 3 순서대로 하면서 계산하면 되는 거 아닌가? 라고 생각했다.

근데 틀려서 찾아보니깐 10의 경우 바로 2로 나누는 것보다 1 빼고 3으로 나누는 게 더 작은 횟수로 문제를 풀 수 있다.어떻게 풀어야 할지 몰라서 다른 분들이 올린 글을 읽고 문제를 풀었다.

 

도움 받은 곳

백준 1463번 1로 만들기 C언어

 

백준 1463번 : 1로 만들기

 

답

#include <stdio.h>
#define SIZE 1000000 + 1
#define MIN(a,b) (a < b ? a : b)

int X;
int D[SIZE];

void solution()
{
	D[0] = D[1] = 0;
	int temp = 0;
	for (int i = 2; i <= X; i++)
	{
		//3번 연산 1회 + 이미 구해둔 최적의 횟수가 최적의 답일 것
		D[i] = D[i - 1] + 1; 
		//하지만 1번이나 2번 연산이 가능한 수라면, 
		//3번 연산을 하는 건 비효율적일 수 있음
		//따라서 최적의 횟수를 각각 구해본 뒤에 더 작은 숫자로 결정해야 함
		if (i % 3 == 0) 
		{
			//1번 연산 1회 + 이미 구해둔 최적의 횟수가 최적의 답일 것
			temp = D[i / 3] + 1; 
			D[i] = MIN(D[i], temp);
		}
		if (i % 2 == 0)
		{
			//2번 연산 1회 + 이미 구해둔 최적의 횟수가 최적의 답일 것
			temp = D[i / 2] + 1;
			D[i] = MIN(D[i], temp);
		}
	}
	printf("%d", D[X]);
}

int main() 
{
	scanf("%d", &X);
	solution();
}

 

문제 풀러가기

1463번: 1로 만들기