< 백준 BaekJoon : 1463번 1로 만들기 > C++

<< 문제 >>

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

1463번: 1로 만들기

 

DP를 이용한 문제입니다.

 

10이 주어졌을 때, 우리는 3가지만 비교해보면 됩니다.

1. 3으로 나눈 경우 => 나누어 떨어지지 않기에 패스

2. 2로 나눈 경우 => 5     -> 5의 최소값을 알아야 함

3. 1을 뺀 경우 => 9         -> 9의 최소값을 알아야 함

 

이렇다면 5의 최소값과 9의 최소값을 비교해야 하는 상황이 나옵니다.

 

그럼 5의 최소값과 9의 최소값을 알고 있는 편이 좋겠죠?

 

이를 위해서 1부터 입력받은 숫자까지 최소값을 채워나가면서 배열에 저장합니다.

 

그럼 배열의 한 칸을 채울때 3가지 경우만 비교해주면 되는겁니다.

 

 

<< 코드 >>

 

#include <iostream>
using namespace std;


int arr[1000001];

void fillTable(int num) {
	arr[0] = 2000000000;
	arr[1] = 0;
	arr[2] = 1;
	arr[3] = 1;

	int op1, op2, op3;
	int min;
	for (int i = 4; i < num+1; i++) {
		op1 = 0;
		op2 = 0;
		op3 = i - 1;
		if (i % 2 == 0) {
			op1 = i / 2;
		}

		if (i % 3 == 0) {
			op2 = i / 3;
		}

		min = arr[op1];
		if (arr[op2] < min) {
			min = arr[op2];
		}
		if (arr[op3] < min) {
			min = arr[op3];
		}

		arr[i] = min + 1;
	}
}

int main() {

	int num;
	cin >> num;

	fillTable(num);
	cout << arr[num];
}

 

 

 

<< 깃헙 >>

 

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/1463.%E2%80%851%EB%A1%9C%E2%80%85%EB%A7%8C%EB%93%A4%EA%B8%B0