[백준][1463] 1로 만들기



[1463] 1로 만들기

문제


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

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

입력


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


출력


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


입력 1

2

출력 1

1

입력 2

10

출력 2

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번만에 만들 수 있다.


1. 문제 설명


  • 해당 문제는 DP로 푸는 문제이다.
  • 나는 Bottom-Up 방식을 이용하여 풀었다. (아래부터 올라오는 반복문 형식)

  • 예시로 n = 6 일 경우,
    dp[1] = 1, dp[2] = 2, dp[3] = 1, dp[4] = 2, dp[5] = 3, dp[6] = 2 가 되도록 한다. dp[6]dp[3] = 1 값을 얻어와서 +1 해주는 형식으로 코드를 짰다.

  • [점화식]
    1번 규칙 (3으로 나누어 떨어진다) : dp[n] = dp[n / 3] + 1
    2번 규칙 (2로 나누어 떨어진다) : dp[n] = dp[n / 2] + 1
    3번 규칙 (1을 뺀다) : dp[n] = dp[n - 1] + 1

2. 소스 코드


#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

	cout << dp[n] << endl;
	return 0;
}



© 2019. by mintheon

Powered by mintheon