[BOJ] 1463 1로 만들기

 

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

1463번: 1로 만들기

알고리즘: DP, DFS

시간복잡도: O(logN)

 

문제는 Dynamic 이긴 한데... N 조건이 작기도(10^6) 하고,

취하는 연산이 계속 나누는거여서 DFS로도 충분히 빠르게 풀리긴 함.

 

Dynamic 접근:

1. 연산을 사용하는 횟수의 최솟값을 출력

2. 답이 이전 부분 문제들에 영향을 받음.

 -> ex) N = X*2 라고 하자. N의 최소 연산 횟수를 알려면 그 전에 X의 최소 연산 횟수를 알아야한다.

 

 

정수 X에 대한 3가지 연산을 잘 관찰하면 점화식을 아래와 같이 정리할 수 있다.

D[X] = Min(D[X/3] + X%3 + 1, D[X/2] + X%2 + 1)

 

이대로 Dynamic 혹은 DFS를 돌리면 됨.

 

DFS

#include <stdio.h>
int N;
int Dp(int n)
{
	int a, b;
	if (n <= 1)
		return 0;
	a = Dp(n/2) + n%2 + 1;
	b = Dp(n/3) + n%3 + 1;
	
	return (a<b)?a:b;
}
int main(int argc, char* argv[]) {
	scanf("%d",&N);

	printf("%d",Dp(N));
	return 0;
}

 

Dynamic

이 코드를 짤 당시에는 3가지 연산을 2가지 연산으로 줄이기 전이라서 점화식이 약간 다름.

#include <stdio.h>
#define	_N 1000001
int N, D[_N];
int i;
int min(int a, int b){ return (a<b)?a:b; }
int main(int argc, char* argv[]) {
	scanf("%d",&N);
	D[1] = 0; D[2] = 1; D[3] = 1;
	
	for (i = 4; i <= N; i++)
	{
		D[i] = D[i-1] + 1;
		if (i%2 == 0)
			D[i] = min(D[i], D[i/2] + 1);
		if (i%3 == 0)
			D[i] = min(D[i], D[i/3] + 1);
	}
	
	printf("%d",D[N]);
	return 0;
}

 

 

---

심화 문제: 12852 1로 만들기 2, https://www.acmicpc.net/problem/12852