[백준] 1463번 - 1로 만들기

여태까지 나는 코딩을 감으로만 또 막풀기만 한 것 같다.

DP(Dynamic Programming)에서 제일 중요한 것이 점화식 세우기라는 것을 이제야 제대로 이해했다.

문제의 각 규칙을 공식으로 만들고, 이것을 하나의 수학식으로 만드는것이 점화식이었다.

1463번 문제는 DP방법중 메모이제이션을 이용해서 풀면 최적화된 답이 나왔다.

내 코드 - 정답 못맞춤(점화식 사용X)

#include <iostream>
using namespace std;
 
long long c;
vector<long long> v;
long long minDiv(int N)
{
    if (N <= 1) return N;
    
    long long three, two,mi;
    three = (N % 3) + (N / 3);
    two = (N % 2) + (N / 2);
    if (three <= two) { mi = 3; c += (N % 3); }
    else if(two < three) mi = 2;
    N /= mi;
    c++;
 
    return N;
}
 
int main()
{
    long long N;
    cin >> N;
    while ((N = minDiv(N)) > 1);
    cout << c << endl;
    return 0;
}
 

---

정답 코드(점화식,메모이제이션 사용)

(이 블로그를 참고하였습니다. 감사합니다.)

문제

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

풀이과정

(1) 규칙

1. X가 3으로 나누어 떨어지면, 3으로 나눈다 : D[N] = D[N/3]+1

2. X가 2로 나누어 떨어지면, 2로 나눈다 : D[N] =D[N/2]+1

3. 1을 뺀다 : D[N] = D[N-1]+1

(2) 순서

작은 문제서 부터 큰 문제를 풀어가는 방식입니다.

숫자 1에서 부터

2로 갈때의 경우 중 가장 작은 방법을 메모이제이션에 저장,

3으로 갈때의 경우중 작은 방법을 메모이제이션에 저장....

N까지 반복합니다.

(3) 코드

#include <iostream>
#include <algorithm>
using namespace std;
 
long long c;
int memo[1000001];//메모이제이션
 
int main()
{
    int N;
    cin >> N;
    
    //bottom-up
    /*
    N%3==0 then N/=3 -> D[N] = D[N/3]+1
    N%2==0 then N/=2 -> D[N] = D[N/2]+1
    N-- -> D[N] = D[N-1]+1
    */
    memo[1] = 0;//1일때는 정답이므로 횟수X
    for (int i = 2; i <= N; i++)
    {
        memo[i] = memo[i - 1] + 1;
        if (i % 3 == 0)
            memo[i] = min(memo[i],memo[i / 3] + 1);//1더한값이 작은지 i/3+1값이 작은지
        if (i % 2 == 0)
            memo[i] = min(memo[i], memo[i / 2] + 1);//1더한값이 작은지 i/2+1값이 작은지
    }
    cout << memo[N] << endl;
    return 0;
}