백준 1463 c++ 1로 만들기

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

1463번: 1로 만들기

---

문제

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

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

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

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int N;
	cin >> N;//정수 입력받기
	vector<int> dp(N+1);//정수가 1로 갈 때 까지 횟수 저장
	dp[1] = 0;//1은 그대로 0
	for (int i = 2; i < N + 1; i++)
	{
		if (i % 2 != 0 && i % 3 != 0)//2와 3으로 둘다 안나누어 지면
		{
			dp[i] = dp[i - 1] + 1;//1을 뺀다
		}
		else if (i % 2 == 0 && i % 3 == 0)//2,3으로 다 나누어질경우
		{
			dp[i] = min(dp[i / 2] + 1, dp[i / 3] + 1);//둘중에 작은걸로
		}
		else if (i % 2 == 0)//2로만 나누어질경우
		{
			dp[i] = min(dp[i - 1] + 1, dp[i / 2] + 1);//1빼거나 2로 나눔
		}
		else if (i % 3 == 0)//3으로만 나누어질경우
		{
			dp[i] = min(dp[i - 1] + 1, dp[i / 3] + 1);//1빼거나 3으로 나눔
		}
	}
	cout << dp[N];
}

---

총 4개의 case를 생각한다

1. 2,3 아무것도 안나누어 떨어질 경우

2. 2로만 나누어질 경우

3. 3으로만 나누어질 경우

4. 2, 3 둘다 나눌 수 있는 경우

 

10의 경우 먼저 나누게 되면

10->5->4->2->1

총 4번을 거치게 되는데

 

1을 먼저 빼고 시작하면

10->9->3->1

3번만 거치게 되므로 무작정 나누기를 먼저 하면 안된다.