백준 1463 (점화식)

1463번: 1로 만들기

과정

• 백준 2839처럼 한 숫자에 대해 지지고 볶아서 최소한으로 원하는 결과를 만드는 유형으로 파악했다.
• 즉, 마지막 수는 2를 만들어서 1로 빼주는 과정으로 진행되어야 한다.

#include <iostream>

using namespace std;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

   

    int N = 0;  // 정수 N

    int count = 0;  // 최종적으로 N을 1로 만드는데 연산한 횟수

    cin >> N;

    while (N != 1)  // 최종적으로 2를 만들어야하기때문

    {

        // N이 3으로 나누어 떨어지는 경우

        if (N % 3 == 0)

            N = N / 3;

        // N이 2로 나누어 떨어지는 경우

        else if(N % 2 == 0)

            N = N / 2;

        else

            N = N - 1;

       

        cout << N;

        count++;

    }

   

    cout << count;

    return 0;

}

 

• 이 코드의 문제가 있다. N = 10 이라고 가정했을 때, 
  10/2 → 5-1 → 4/2 → 2-1 이렇게 4번을 진행하지만, 최소 연산은 10-1 → 9/3 → 3/3 으로 3번에 끝낼 수 있다.
• 즉, 백준 2839의 다른 방법은 DP를 이용해야한다는 것을 깨달았다.
• 내가 기억하는 DP는 점화식을 찾아내서 최소값을 골라내는 느낌이었다.

• 먼저 하이라이트 한 숫자 = 소수를 보면 유독 숫자가 튄다.
  여기서 알아 차린 점이 현재 숫자-1을 하면 이전 숫자의 연산처럼 진행하면 되므로
  현재 숫자의 최종 횟수는 최대 이전숫자 최종 횟수 + 1 임을 알 수 있다.
• 근데 위에 있는 공식이 안먹히는 대표적인 숫자가 보인다. 바로 8.
  그래서 연산과정을 보니, 7같은 경우 이전 숫자를 만들기 위해 -1을 해줬다면, 8은 2로 나눠서 4를 만들었고, 그때부턴 4의 연산과 같다.
  즉, 현재 숫자가 2 또는 3으로 나누어지는 경우, 2와 3을로 나눈 숫자의 연산횟수 + 1 임을 알 수 있다.

 

2가지 경우를 토대로 코드를 짜는데, 문제에서 N은 1보다 크거나 같고, 10^6보다 작거나 같은 정수라고 했으므로,

 

배열을 10^6 +1 크기만큼 만들어서 인덱스 = N으로 만들고 min()으로 비교해서 대입하려고 한다.

#include <iostream>

using namespace std;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int N = 0;  // 정수 N

    int dp[1000001];  // 최종적으로 각 인덱스 N을 1로 만드는데 연산한 최소횟수

    cin >> N;

    dp[1] = 0;

   

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

    {

        // 최종 연산의 기본 최소값(이거보다 작거나 같아야함)

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

        // 3으로 나눠질 경우

        // 3으로 나누는게 더 최소 연산 횟수이므로 먼저 조건문 실행

        if (i % 3 == 0)

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

        // 2로 나눠질 경우

        if(i % 2 == 0)

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

    }

    cout << dp[N];

    return 0;

}