[DP] Ch08-2

08-2| 1로 만들기

🌼 문제풀이 방법:

n이 10일 경우를 생각해 보자! 이때 우리는 1을 뺐을 경우, 2로 나누어지므로 2로 나눴을 때의 경우, 5로 나누었을 때의 경우를 생각해 보아야 하고, 각각의 경우에 대해서도 계산을 해서 가장 작은 값을 확인해야 한다.

즉, 피보나치 수열 문제에서처럼 f(2)와 같은 경우가 여러 번 호출된다. 따라서 이 문제를 bottom-up 방식으로 풀어보겠다.

🌷 코드:

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

int n = 0;
vector<int> d(30000);

int main() {
	int n = 0;
	cin >> n;
	int cnt = 0;
	for (int i = 2; i <= n; i++) {
		d[i] = d[i - 1] + 1; 	// 이전까지 호출에서 1을 빼는 연산을 먼저 계산

		// 만약 그 수(i)가 나누어 떨어지면
		// 각각 나눈 숫자의 연산 횟수와, 현재 연산 횟수를 비교해서
    // 둘중의 최솟값을 취함

		if (i % 2 == 0) {
			d[i] = min(d[i], d[i / 2] + 1);
      // d[i/2]+1은 2로 나눈 연산을 더한 d[i/2]까지의 연산 횟수를 의미
		}
		if (i % 3 == 0) {
			d[i] = min(d[i], d[i / 3] + 1);
		}
    if (i % 5 == 0) {
      d[i] = min(d[i], d[i / 5] + 1);
    }
	}
	cout << d[n];
	return 0;
}

• BOJ 36
• Algorithm 12
• CodingTest 11
• Web 9
• Javascript 8
• Vue 7
• React 7
• DBProject 4
• Python 3
• Tech-interview 3
• Express 3
• Next 3
• Github 2
• Django 2
• C 1
• C++ 1
• WebGame 1