DP > 1로 만들기(1463번)

문제 설명

---

풀이

이거 사실 백준 알고리즘 강의때 들은거임

그때 푼거라고...

방학내내 공부하는 내모습에 취해서 풀었다고 자부했는데

다시 푸니까 못푸는 나는... 개똥벌래,,,

 

암튼 다시 고민을 해보았지

탑다운은 재귀함수로, 바텀업은 1부터 답 나올떄까지 반복문으로 구하면 된다

그리고 DP는 점화식을 구하는게 제일 중요하다

피보나치마냥 반복해서 구해야되는데 한번 구한 값은 또 안구하는게 원칙!!

그러려면 메모이제이션 할 배열이랑 계산하기 위한 점화식이 필요한거다

그래서 이 문제도 점화식만 구하면 쉬운거였는데 그게 어렵더라...

공부하자 야미지원,,,!

 

이제 본격적으로 풀이에 대해 말하자면,

우선 얘는 3가지 방식이 있어

1뺴기, 2나누기, 3나누기

근데 1빼기는 제약 조건없이 다 할수 있자나

그래서 얘가 비교 기준이 될거야

일단 1빼기가 되었을 떄로 잡는거지

 

먼저 점화식 세우기 전에 메모배열 정한느데 얘는 d[n]이라고 할게

여기서 d[n]은 n이 1이 되기 위한 최소 횟수를 말해!

그럼 d[1]은 뭐겠어 0이지~ 왜냐고? 이미 1이니까!!!

암튼!

그럼 점화식은 총 3가지가 존재하겠지?

• d[n] = d[n/3] + 1
• d[n] = d[n/2] + 1
• d[n] = d[n-1] + 1

여기서 1빼기가 기준이 되니까 마지막거 먼저 d[n]에 대입하구, 조건 비교해가면서 작으면 바꾸고 아니면 넘기고

이걸 반복문으로 반복하면돼!

바텀업은 d[1]부터 시작해서 반복문의 i가 2부터 n까지 반복시켜서 구하고,

탑다운은 d[n]부터 거꾸로 돌면서 재귀함수로 구하는거야

이미 d[n]에 값이 저장되어있으면 그거 return (같은 문제는 다시 안푸는게 DP의 장점!)

아니면 재귀로 구해서 return!

자세한건 아래 코드 봐주세용

 

---

요건 bottom-up

// Bottom-up
#include <iostream>
#include <stdio.h>
#define MAX 1000000
using namespace std;

//Bottom-up
int main()
{
    int n;
    int d[MAX];
    cin >> n;
    d[1]=0;
    for(int i=2;i<=n;i++)
    {
        d[i]=d[i-1]+1; //1씩 감소(기본값)
        if(d[i]>d[i/2]+1 && i%2==0)
        {
            d[i]=d[i/2]+1;
        }
        if(d[i]>d[i/3]+1 && i%3==0)
        {
            d[i]=d[i/3]+1;
        }
    }
    printf("%d\n", d[n]);
    return 0;
}

 

요건 top-down

// Top-down
#include <iostream>
#include <stdio.h>
#define MAX 1000000
using namespace std;

//Top-down : 재귀함수 활용
int d[MAX];
int go(int n) {
    if(n==1) return 0;
    if(d[n]>0) return d[n];
    d[n] = go(n-1)+1;
    if(n%2==0 && d[n]>go(n/2)+1)
    {
        d[n]=go(n/2)+1;
    }
    if(n%3==0 && d[n]>go(n/3)+1)
    {
        d[n]=go(n/3)+1;
    }
    return d[n];
}
int main()
{
    int n;
    d[MAX]={0, };
    cin >> n;
    printf("%d\n",go(n));
    return 0;
}