[1463] 1로 만들기

---

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

1463번: 1로 만들기

 

 

오랜만에 다이나믹 프로그래밍 문제!

 

먼저 범위를 설정하고 메모이제이션을 이용해야 하므로 배열을 선언해주었다.

int A[1000001];

A[0]은 안 씀!

 

그리고 직접 써보면서 규칙을 찾아보았다.

1~3은 초기값

직접 배열을 채워보면서 규칙을 찾았다.

1을 빼고 바로 전 값의 A[i-1]을 더하는 경우가 있고,

3을 나누고 A[i/3]을 더하는 경우가 있고,

2를 나누고 A[i/2]을 더하는 경우가 있었다.

 

그리하여 아래와 같은 규칙을 완성하였다.

이를 코드로 작성하면 아래와 같다.

	for (int i = 4; i <= N; i++) {
		int min1 = 0; 
		int min2 = 1000000; 
		int min3 = 1000000;

		min1 = 1 + A[i - 1];
		if (i % 3 == 0) { // 3으로 나누어 떨어지면
			min2 = 1 + A[i / 3];
		}
		if (i % 2 == 0) { // 2로 나누어 떨어지면
			min3 = 1 + A[i / 2];
		}

		A[i] = min(min1, min(min2, min3));
	}

min1, min2, min3을 만들고 이 중에 최솟값을 찾아 A[i]에 넣어주는 알고리즘을 만들었다.

 

min2와 min3이 100000인 이유는 혹여나 3의 배수/2의 배수가 아닐 경우 if문에 들어가지 않기 때문에 임의로 큰 값을 설정해준 것이다.

 

전체 코드는 아래와 같다.

#include <iostream>
#include <cmath>
using namespace std;

int N;
int A[1000001] = { 0, 0, 1, 1, };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 4; i <= N; i++) {
		int min1 = 0; 
		int min2 = 1000000; 
		int min3 = 1000000;

		min1 = 1 + A[i - 1];
		if (i % 3 == 0) { // 3으로 나누어 떨어지면
			min2 = 1 + A[i / 3];
		}
		if (i % 2 == 0) { // 2로 나누어 떨어지면
			min3 = 1 + A[i / 2];
		}

		A[i] = min(min1, min(min2, min3));
	}

	cout << A[N];
}