[백준 1463 | C++] 1로 만들기 :: DP

😴문제 링크

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

---

💡아이디어 단계

1. 3으로 나누는 연산을 가장 많이 하면 되는 거 아닌가?
   -> 2로 나누는 연산을 고려하지 않음
   
   
2. 10이라면, -1할 수도 있고 2로 나눌 수도 있는데 둘 중에 뭘 해야하는 거지....... 두 경우를 모두 계산해봐서 비교하면 되나?
   
   
3. 그러면 -1을 뺀 9까지의 최소 연산 횟수랑 2로 나눈 5까지의 최소 연산 횟수를 비교하면 되는 거 아닌가? 어차피 9에서 10만드나 5에서 10만드나 연산은 1번만 더하면 되는 거니까! 이거를 1-10까지 각 수마다 반복해서 계산해두면 편하겠다.
   
   
4. 정수 n을 입력받으면 (n-1)까지의 최소 연산 횟수를 모두 미리 계산해서 저장해두고, 필요한 수를 갖다 쓰자. -> dp 문제

---

💻코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> dp(n+1, 0);	// n+1을 더한 이유 : 인덱스와 정수의 일치
	dp[1] = 0;	// 1에서 1 만들기 : 0번
	dp[2] = 1;	// 2에서 1 만들기 : 2로 나누기 -> 1번

	for (int i = 3;i <= n;i++) {
		int tmp1 = i;	// i로 초기화
		int tmp2 = i;
		int tmp3 = i;
        
		tmp1 = dp[i - 1] + 1;	// 1을 더하는 경우
        
		if (i % 2 == 0) {	// 2의 배수
			tmp2 = dp[i / 2] + 1;
		}
		
		if (i % 3 == 0) {	// 3의 배수
			tmp3 = dp[i / 3] + 1;
		}

		dp[i] = min(tmp1, tmp2);
		dp[i] = min(dp[i], tmp3);
	}

	cout << dp[n];
}

🐱부연 설명

• 벡터의 원소를 (n+1)개 만든 이유: 크기 n의 벡터일 경우, 인덱스는 0부터 n-1까지 있으므로 정수 n의 최소 연산 횟수는 dp[n-1]에 저장된다. 즉 10의 최소 연산 횟수는 dp[9]에 저장. 헷갈린다!! 따라서 (n+1)크기로 만들어서 n의 최소 연산 횟수를 dp[n]에 저장한다.
  
  
• tmp1, 2, 3을 i로 초기화하는 이유: 정수 i을 1로 만드는 최대 연산 횟수는 -1을 (i-1)번 하여 1로 만드는 경우이다. 문제에서는 최소 연산 횟수를 구하는 경우이므로 횟수(tmp)를 절대 답이 아닐 것 같은 매우 큰 수로 초기화해두고, 더 작은 경우의 수가 나올 경우 그 값으로 교체해준다. (i-1) < i 이므로 i로 초기화해도 상관없다. (i-1)보다 i가 더 깔끔한 느낌이라...

 

⚠️실수 포인트

1. tmp의 초기화 위치

: for문 안쪽에서 초기화를 해야한다. for문 바깥에서 초기화를 해서 값이 제대로 나오지 않은 것인지 확인하자.

2. i와 n 헷갈림

: 우리는 dp[i]를 통해 배열의 값을 저장하여 마지막에 dp[n]의 값을 출력하는 것이다.

3. min 함수

: 인자를 2개 받는다. 3개 불가능..... 3개의 값을 비교하려면 min 함수 2번 쓰기