[백준 C++] 1463 1로 만들기 - 다이나믹프로그래밍

1463번: 1로 만들기

 

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

static int minOp[1000001];

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

	minOp[2] = minOp[3] = 1;
	for (int i = 4; i <= n; ++i)
	{
		int op3 = 100, op2 = 100, op1 = 100;

		if (i % 3 == 0)
		{
			op3 = min(minOp[i / 3], minOp[i - 1]) + 1;
		}

		if (i % 2 == 0)
		{
			op2 = min(minOp[i / 2], minOp[i - 1]) + 1;
		}

		op1 = minOp[i] = minOp[i - 1] + 1;

		minOp[i] = min(min(op3, op2), op1);
	}

	cout << minOp[n];
}

---

첫 DP 문제입니다.

주의해야 할 점이 두 가지 있었습니다.

 

1. n이 3 또는 2로 나누어 떨어지지만 1 빼기 연산을 사용하는 것이 더 최솟값일 경우 존재

2. n 6으로 나누어떨어지는 경우(3나누기, 2나누기 연산에 모두 해당하는 경우) 존재

 

따라서 if ~ else if 문을 사용하는 것이 아니라

3으로 나눴을 때, 2로 나눴을 때, 1을 뺐을 때의 연산 횟수를 각각 구한 다음

셋 중 최솟값을 선택하는 방법을 사용했습니다.