[백준] | C++ | 1463. 1로 만들기

개요

실버 4 를 달았습니다.

실버 4 를 달면서 C++을 대충 맛봤는데 세상에 C#보다 몇배는 빠릅니다!!!

 

알고리즘은 C#으로 풀면 안돼요..

 

저번 글은 4673. 셀프 넘버를 풀었었는데 실버 5 따리 개 쉬운 문제였더라구요.

그런 의미로 실버 4 도 달았겠다 이번 글은 1463. 1로 만들기 라는 실버 3 문제를 풀어보도록 하겠습니다.

 

 

---

 

 

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

문제가 짧습니다.
하지만 딱봐도 어려워 보이는군요... 알고리즘 분류는?

친구가 백준을 풀때 항상 기피하던 분류던데 대충 찾아보니 딱봐도 어려워 보이는군요...

 

 

---

 

 

풀이

일단 간단하다면 간단한 문제 입니다.

최솟값을 구하기 전에 대충 뇌빼고 구현해봅시다.

int n;
cin >> n;

while(n != 1)
{
	if(n % 3 == 0)
    	n /= 3;
    else if(n % 2 == 0)
    	n /= 2;
	else
    	n--;
}

cout << n;

 

하지만 이렇게 만들면 당연히 안되겠죠.

 

3으로 나누어 떨어지더라도 2로 나눌 수 있는거고
3이나 2로 나누어 떨어지더라도 1을 빼버릴 수도 있는겁니다.

 

그렇기 때문에 우선순위 없이 모든 경우의 수를 대입해보는게 맞겠죠.

 

하지만 알고리즘 분류는 다이나믹 프로그래밍(DP) 입니다.
이미 나온 결과를 활용해서 이래저래 연산 횟수를 줄이는 방법인데 이걸 어떻게 활용해야할지 저로썬 감잡기가 어려웠습니다.

 

일단 이미 나온 결과를 저장해야하는데 결과만 저장할게 아니라 과정도 저장해야겠죠.

 

이 쯤 생각이 닿았을때 그냥 실버4 문제나 풀까 진지하게 고민했습니다.

 

...

일단 코드고 뭐고 구상부터 해봅시다.

 

방법 3가지중에 가능한걸 먼저 찾습니다.

1을 빼는건 어느 경우에도 가능하니 제외하고 3이나 2로 나눌 수 있는지를 알아내야겠죠.

 

알아낸 다음 분기를 최대 3개로 나누어 나온 값들을 저장한다음 그 값을 다시 계산하고...

30을 넣는다고 가정하고 그림을 그려보면 이런식으로 계산을 계속해서 할텐데...

 

이렇게 되면 DP고 뭐고 경우의 수가 몇갭니까.

 

차라리 1부터 쭉 올라가는게 더 나을수도 있다고 생각했습니다.
아, 물론 1은 그 자체니까 제외하고.

 

2부터 올라간다고 해도 각자의 경우의 수를 전부 돌긴 빡세니까

3은 최소 연산이 1개고 4는 2개고... 하는걸 저장해 놓은 배열을 실시간으로 만들면서 활용하는게 맞는 것 같았습니다.

 

그렇게 되면 만약 5가 들어온다면 5는 2나 3으로 나누어 떨어지지 않으니까 5에서 1을 뺄거고
dp배열에 4번째 값은 2니까 dp배열의 5번째 값으로 3이 들어가게 되는거죠.

 

큰 값을 계산하기 위해서 이미 계산된 작은 값들을 이용하는 느낌으로다가..

 

그래서 대충 구상해보면

 

일단 int 배열 dp를 만듭니다.
그리고 2부터 시작하는 index가 n까지 증가하는 for문을 돌립니다.

 

-1을 하는 연산은 어떤 숫자던 무조건 하는거니 일단 dp[i]에다가 dp[i-1] + 1을 넣고

 

만약 2로 나누어 떨어진다면
현재 들어가있는 dp[i]와 dp[1/2] + 1 둘 작은 값을 채택하면 되겠죠.

 

3으로 나누어 떨어지는경우도 마찬가지구요.

 

코드는...

#include<iostream>
#include<algorithm>

using namespace std;

int dp[1000000];

int main()
{
	int n;
	cin >> n;
	dp[1] = 0;
	for (int i = 2; i <= n; i++)
	{
		dp[i] = dp[i - 1] + 1;
		if (i % 2 == 0)
		{
			dp[i] = min(dp[i], dp[i / 2] + 1);
		}
		if (i % 3 == 0)
		{
			dp[i] = min(dp[i], dp[i / 3] + 1);
		}
	}
	cout << dp[n];
}

이런식으로 했습니다.

 

결과는?

1트만에 바로 정답!!

사실 제출하면서 i가 아니라 1을 3으로 나눈 나머지를 구하고
dp[n]이 아니라 그냥 n을 출력하는 등의 이상한 짓으로 인해 3트 성공이지만 아무튼 1트입니다.

 

 

---

 

 

마치는 말

생각보다 dp 별거 업군요.

 

아닌가?

골드에서 뵙겠습니다. 감사합니다.