[Algo Rhythm🕺💃] BOJ 1463 - 1로 만들기

💫문제 분석

주어진 $n\ (1 \le n \le 10^6)$에 대하여 사용가능한 연산들은 다음과 같다.

• $op_1 : n \equiv 0 \pmod{3}이면,\ n = n \div 3$
• $op_2 : n \equiv 0 \pmod{2}이면,\ n = n \div 2$
• $op_3 : n = n - 1$

그리고 $n$을 1로 만들기 위해 사용하는 연산의 최소 횟수를 $f(n)$이라고 하자.

 

$n$에 대하여 $op_1,\ op_2,\ op_3$을 모두 사용할 수 있을 때 $n$을 1로 만들기 위해 사용하는 연산의 최소 횟수를 각각 $f_1,\ f_2,\ f_3$라고 하자.

그렇다면 $n \equiv 0 \pmod{3}$이면 $op_1$을 사용하여 $n$을 $n \div 3$으로 줄일 수 있기 때문에 $f_1 = f(n \div 3) + 1$이다.

그리고 $n \equiv 0 \pmod{2}$이면 $op_2$를 사용하여 $n$을 $n \div 2$로 줄일 수 있기 때문에 $f_2 = f(n \div 2 ) + 1$이다.

마지막으로 모든 $n$은 $op_3$를 사용하여 $n$을 $n - 1$로 줄일 수 있기 때문에 $f_3 = f(n - 1) + 1$이다.

따라서, $f(n) = \min(f_1,\ f_2,\ f_3)$이다.

 

🔥문제 풀이

$f(n)$을 점화식으로 표현하면 다음과 같다.

$f(n)= \begin{cases} 0 & if\ n = 1\\ \min(f_1,f_2,f_3) & else \end{cases}$

 

✨복잡도 분석

주어진 $n\ (1 \le n \le 10^6)$에 대하여 시간 복잡도와 공간 복잡도는 각각 다음과 같다.

 

⏰시간 복잡도 : $O(n)$

$f(i)\ (1 \le i \le n)$을 모두 계산해야 하기 때문에 $O(n)$이 소요됨.

🏠공간 복잡도 : $O(n)$

$f(i)\ (1 \le i \le n)$을 저장할 공간이 필요하기 때문에 $O(n)$이 소요됨.

 

🌈코드

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	const int MAX = 1e6 + 1;
	int mem[MAX];
	int main()
	{
	int x, f1, f2, f3;
	scanf("%d", &x);
	mem[1] = 0;
	for(int i = 2; i <= x; i++)
	{
	f1 = (i % 3 == 0) ? mem[i / 3] + 1 : MAX;
	f2 = (i % 2 == 0) ? mem[i / 2] + 1 : MAX;
	f3 = mem[i - 1] + 1;
	mem[i] = min(min(f1, f2), f3);
	}
	printf("%d", mem[x]);
	return 0;
	}

view raw boj1463.cpp hosted with ❤ by GitHub

 

 

🌏문제 출처

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

1463번: 1로 만들기