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

문제링크 : https://www.acmicpc.net/problem/1463

 

문제풀이

동적 계획법(Dynamic programming)으로 풀 수 있는 문제이다.

2와 3은 각각의 수로 나눠지므로 1로 저장해놓았는데,

어차피 계산 결과 1이 나오니 1로 초기화해놓을 필요는 없을 것 같다.

 

4인 경우부터 예를 들어보면 다음과 같다.

 

예) 4의 연산 횟수 최솟값

① 4는 2로 나눠지므로 2로 나눈다. --- 1번

② 2에서 1을 빼면 (혹은 2로 나누면) 1이 된다. --- 1번

 

②번의 경우 2에서 1이 되는 횟수는 1번으로, 이미 배열에 횟수를 저장해놓았다.

따라서 arr[2]의 값에 1을 더하면 4의 연산 횟수 최솟값이 된다.

 

예) 5의 연산 횟수 최솟값

① 5는 3, 2로 나눠지지 않으므로 1을 뺀다. --- 1번

② 4는 2로 나눠지므로 2로 나눈다. --- 1번

③ 2에서 1을 빼면 (혹은 2로 나누면) 1이 된다. --- 1번

 

②과 ③번의 경우는 데이터가 4일 때 이미 반복된 경우이다. 따라서 계산할 필요없이 arr[4]값을 가져다 쓰면 된다.

arr[4]의 값에 1을 더하면 5의 연산 횟수 최솟값이 된다.

 

예) 10의 연산 횟수 최솟값

① 10은 2로 나눠지므로 2로 나눈다. --- 1번

②,③,④ 데이터가 5일 때 이미 반복된 경우이다. --- 3번

 

앞의 예시들을 그대로 적용하면 10의 연산 횟수의 최솟값은 4이다.

하지만 10은 10 - 9 - 3 - 1 로 3번의 연산이 가능하다.

이 경우를 통해 2, 3으로 나누어 떨어진다고 하더라도, 1을 먼저 빼야 최솟값이 구해지는 경우도 있다는 것을 알 수 있다.

따라서 횟수를 구할 때,

2와 3으로 먼저 나누는 경우 / 1을 먼저 빼는 경우의 결과를 비교해보고 더 작은 횟수를 출력하면 된다.

 

 

소스코드

/*
 * 백준 1463번: 1로 만들기
 */

#include <iostream>

using namespace std;

int main() {
	int N;
	cin >> N;

	if (N == 1) {
		cout << 0;
	}
	else if (N < 4) {
		cout << 1;
	}
	else {
		int* arr = new int[N + 1];
		arr[0] = arr[1] = 0;
		arr[2] = arr[3] = 1;

		for (int i = 4; i <= N; i++) {
			int value = arr[i - 1];
			if (i % 3 == 0) {
				value = arr[i / 3] < value ? arr[i / 3] : value;
			}
			else if (i % 2 == 0) {
				value = arr[i / 2] < value ? arr[i / 2] : value;
			}

			arr[i] = value + 1;
		}

		cout << arr[N];

		delete[] arr;
	}

	return 0;
}