[C++]백준 1463번: 1로 만들기

문제

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

1463번: 1로 만들기

 

문제이해

 

• 첫째 줄에 N을 입력합니다.
• 연산 횟수의 최솟값을 출력합니다.

 

이 문제는 다이나믹 프로그래밍을 이용해야 합니다. 배열을 통해 설명해 보겠습니다. dp [i]는 i를 1로 만드는데 걸리는 연산 횟수의 최솟값을 의미합니다.

 

dp [2]와 dp [3]은 당연히 1입니다.

 

dp [4]의 경우 dp [2]에 1을 더한 값 또는 dp [3]에 1을 더한 값인 2입니다.

 

dp [5]는 5 - 1 = 4, 4 - 1 = 3, 3 / 3 = 1 또는 5 - 1 = 4, 4 / 2 = 2, 2 / 2 = 1 이러한 연산 과정을 통해 3이라는 값을 가집니다.

 

이렇게 dp [i]는 dp [i-1] 또는 가능하다면 dp[i / 2] 또는 dp [i/3]의 값 중 가장 작은 값에 1을 더한 값을 가지게 됩니다.

 

이를 코드로 표현하면 다음과 같습니다.

 

문제풀이

#include <iostream>
#include <vector>
#include <cmath>
#define MIN 1000001
using namespace std;

vector<long long> dp(MIN);

void method() {
	dp[2] = 1;
	dp[3] = 1;
	for (int i{ 4 }; i < dp.size(); i++) {
		int min{ MIN };
		if (i % 3 == 0)
			if (dp[i / 3] <= min)
				min = dp[i / 3];
		if (i % 2 == 0)
			if (dp[i / 2] <= min)
				min = dp[i / 2];
		if (dp[i - 1] <= min)
			min = dp[i - 1];
		dp[i] = min + 1;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	method();
	int N;
	cin >> N;
	cout << dp[N];
}

 

 

문제후기

어렵지 않은 문제였습니다.