[SCCC] 1로 만들기 1&2

알고리즘 개념

• 동적 계획법
  복잡한 문제를 간단한 문제들로 나누고, 간단한 문제들을 해결한 뒤, 간단한 문제들의 답을 이용해 복잡한 문제의 답을 구함

• 최적 부분 구조(Optiomal Substructure)
  큰 문제의 최적해가 작은 문제의 최적해를 포함한다
  예: 피보나치 수열

• 중복되는 부분 문제
  작은 문제의 답을 여러번 참조한다
  예: 피보나치 수열

1로 만들기_1463번

코드

#include <bits/stdc++.h>
using namespace std;

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

    vector<int> vec = {0, 0};  //set 0 1
    for (int i = 2; i <= n; i++) {
        vec.push_back(vec[i-1] + 1);
        if (i % 3 == 0) vec[i] = (min(vec[i], vec[i/3] + 1));
        if (i % 2 == 0) vec[i] = (min(vec[i], vec[i/2] + 1));
    }
    cout << vec[n];
    
    return 0;
}

풀이노트

• 수를 N 에서 1 로 감소하는 방향이 아니라 1 에서 N 으로 증가하는 방향을 설계해야 함

• 따라서 X-1 을 D[i] = D[i-1] + 1 이라 생각하면서 DP 로 풀어보자

• Greedy 로 풀면 안 되는 문제 유형임

• +1 /2 /3 을 모두 확인하고 가장 작은 값을 저장해야 함
  => v[i] = v[i-1] + 1 을 먼저 저장하고, min(vec[i], vec[i/3]+1)) 또는 min(vec[i], vec[i/2]+1)) 을 확인해야 함

- 예시
2 : 2 1
3 : 3 1
4 : 4 2 1
5 : 5 4 2 1 
6 : 6 2 1
7 : 7 6 2 1
8 : 8 4 2 1
9 : 9 3 1 
10 : 10 9 3 1
11 : 11 10 9 3 1

1로 만들기 2_12852번

코드

#include <bits/stdc++.h>
using namespace std;

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

    vector<int> count = {0, 0};  //연산 횟수의 최소값
    vector<int> num = {0, 0};  //직전값
    for (int i = 2; i <= n; i++) {
        count.push_back(count[i-1] + 1);
        num.push_back(i-1);
        if (i % 3 == 0 && (count[i] > count[i/3]+1)) {
            count[i] = count[i/3] + 1;
            num[i] = i/3;
        }
        if (i % 2 == 0 && (count[i] > count[i/2]+1)) {
            count[i] = count[i/2] + 1;
            num[i] = i/2;
        }
    }
    
    cout << count[n] << "\n";  //최소연산횟수 출력
    while(n > 0) {
        cout << n << " ";  //연산에 포함되는 수 출력
        n = num[n];
    }
    
    return 0;
}

풀이노트

• count : 최소 연산 횟수
• num : 최소 연산이 되는 직전 값
• n이 1이 될 때까지 num[n] 을 따라가면 됨
  • 8 -> 4 -> 2 -> 1