[동적프로그래밍] 백준 1463번 1로 만들기(C++)

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

 

 

오우 1로 만들기 문제!

 

문제는 정말 간단하다

 

3으로 나누거나 2로나누거나 1로빼서 정수 n을 1로 만들때, 몇번 연산을 진행했는지에 대해 최솟값을 출력하라고 하는 것이다.

 

사실이제 사람들이 쉽게 착각할 수 있는것이

 

"그럼 나뉠 수 있는 최대로 나눈 다음에 1로빼면 되는거아님?"

예를들어 3으로 먼저나뉘면 3으로나누고

2로 나뉘면 2로나뉘고

둘다 안되면 1빼고

 

흠..

 

응 아니야

 

근데 나도 그렇게 생각했다

난 멍청해

 

예를들어 우리가 10 이란 숫자가 있다고 보자.

 

2로 먼저 나뉘네? ==5

2와 3으로 안나뉘네? 1마이너스 ==4

2로나뉘네? ==2

1빼네? ==1

 

4번인 반면

 

1먼저 빼준다 =9

3으로 나눠준다 =3

3으로 나눠준다 =1

어라?!

 

1로 먼저 뺏는데 어째서,,, 3번이!!!!!

 

그니까 직관적이지 않다는 것이다.

 

이건 그래서 작은 문제의 집합으로 풀어야 된다는 것

 

특정 숫자 n에 대해서 , 그 숫자 이전값 +1만 하면 되잖아?

#include <iostream>

#include <algorithm>

using namespace std;

int dp[1000001];

int main()

{

    int N;

    cin >> N;

    dp[1] = 0;

    for (int i = 2; i <= N; i++)

    {

        dp[i] = dp[i - 1] + 1;

        if (i % 2 == 0)

            dp[i] = min(dp[i], dp[i / 2] + 1);

        if (i % 3 == 0)

            dp[i] = min(dp[i], dp[i / 3] + 1);

    }

    cout << dp[N] << endl;

}

먼저 1을 뺀 경우부터 생각하고

그 이후에 2로나눈값으로 나눠보고~

3으로 나눈값으로 나눠보고~~ dp를 결정하라 이거다

 

min을 왜쓴진 알겠지? 1뺀값이 더 작을수도 있잖아 위에서 보여준 것처럼

10에 대해서 2로나뉘는데, 1로 뺀값은 3이여 dp[9]=2이란 말여, 그럼 1더했으니까 3인데

dp[10/2]+1 = dp[5] +1=4란 말이여

 

dp의 거의 기초격인 문제이고, 나중에 또 관련되어서 나올 수 있으니 해당 내용은 이해가 안되더라도 꼭 이해하거나 외워야 될듯!