1463

백준 1463번

Link: 1463번: 1로 만들기

---

문제 설명

오늘도 내힘으로 푸는데 실패.

이 문제도 직전에 풀었던 계단문제처럼 점화식이 가장 중요했다.

주어진 조건을 곧이곧대로 썼다가 답없는 상황이 나왔다.

가장 먼저 입력된 수를 3으로 나눠떨어지는지 검사하고 나눠떨어지면 3으로 나누는 것을 첫번째 조건으로 넣었고

3으로 나눠떨어지지 않으면 2로 나눠떨어지는지 검사하고 나눠떨어지면 2로 나누는 것을 두번째 조건으로 넣었다.

이 두가지를 만족하지 않을때 1을 빼는 것으로 3가지 조건을 넣었다.

도무지 어떻게 더 나갈지 모르겠어서 예전 답을 다시 찾아봤다.

예전 답도 구글링해서 답 찾아보고 풀었는데, 1년동안 실력이 전혀 안늘어난 느낌이다.

정답은 우선 1을 뺀 다음, 3으로 나눠떨어지면 3으로 나눴을때와 1을 뺐을때의 DP를 비교하는 것이었다.

3으로 나눠떨어지지 않을 경우, 2로 나눠떨어지면 2로 나눴을때와 1을 뺐을때의 DP를 비교한다.

나머지 경우는 당연히 1을 뺀 값이 DP에 들어간다.

오늘로 DP에서 5문제를 풀고있는데, 문제마다 매번 다른 개념인것 같은 느낌이다.

DP 문제 전반에 걸칠 수 있는 개념이 안잡힌 느낌. 첫술에 배부를수는 당연히 없지만 이대로 갔을때 실력이 늘긴 할지, DP에 대한 접근 방법을 제대로 파악할 수 있긴 할지 매우 걱정된다.

---

정답 코드

//
// Created by Keith_Lee on 07/01/2019.
//

#include <iostream>
#include <string.h>

using namespace std;

int min(int a, int b){
    return a > b ? b : a;
}

int main(){
    int N;
    int DP[1000000];

    cin >> N;

    bzero(DP, sizeof(DP));

    for(int i=2; i<=N; i++){
        DP[i] = DP[i-1] + 1; // 기본적으로 1 빼준다.

        if(i % 2 == 0){
            DP[i] = min(DP[i], DP[i/2] + 1); // 2로 나눠떨어지면 2로 나눴을때와 1뺐을때를 비교한다.
        }
        if(i % 3 == 0){
            DP[i] = min(DP[i], DP[i/3] + 1); // 3으로 나눠떨어지면 3으로 나눴을때와 1뺐을때를 비교한다.
        }
    }

    cout << DP[N] << '\n';

    return 0;
}

---