[C++,DP] 백준 1463번 1로 만들기 문제풀이, DP와 분할정복의 특징

문제링크

백준 1463번 1로 만들기 

1463번: 1로 만들기

 

다시 복습하는 DP문제이다.  다시 DP 개념부터 집고 넘어가야겠다.

 

DP(Dynanic Programing)란? 

주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과들로 큰 문제를 푸는 방법을 말하며 여기서 DP의 Dynanic은 개발자가 아무 의미없이 붙인 거라고 한다... 큰 문제를 해결하기 쉽게 여러 개의 쉬운 부분 문제들을 풀어 해결하는 방법 정도로만 이해하면 될 것 같다.

 

분할정복이랑 비슷한 개념이기는 하나 분할정복은 문제를 분할했을 때 겹치는 문제가 발생하지 않지만, DP는 겹치는 문제가 발생하기 때문에 메모이제이션(Memoization)이라는 새로운 개념을 도입하여 해결한다. 여기서 다이나믹 프로그래밍이 분할정복에 포함되는지 궁금해졌다. 

 

검색해보니 위에서 말한 겹치는 문제 즉, 하위 문제들이 서로 다른문제에게 영향을 미치는지의 유무에 따라서 다이나믹 프로그래밍, 분할정복으로 나눠지는 것이다. 예를 들어, 다이나믹 프로그래밍의 대표적인 문제인 피보나치 수열은 하위문제들이 서로 연관있는(같은) 문제이고 머지쏘트, 유클리드 알고리즘으로 대표되는 분할정복문제는 분할된 문제들이 서로 다른 문제이므로 두 문제가 서로 포함된다기 보다는 공통점과 차이점이 있다는 정도로만 이해하면 될 것 같다.

 

즉, DP문제와 분할정복문제의 공통점은 주어진 문제를 여러 개의 부분(하위) 문제들로 나누어 푼다는 것(Optimal substructure) 
차이점은 그 나누어진 문제들이 서로 관련이 있으면 DP(Overlapping Subproblems)문제 아니라면 분할정복문제이다. 

 

DP를 푸는 방법에는 보통 재귀 호출을 사용하는 탑다운(top-down)방식과 반복문을 사용하는 바텀업(bottom-up)방식이 있는데 나는 배열을 선언해 반복문을 이용 바텀업방식으로 풀었다.

 

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
 
int main(){
    int num;
    cin>>num;
    vector <int> DP(num+1,0);
 
    DP[1]=0;
    DP[2]=1;
    DP[3]=1;
 
    for(int i=4;i<num+1;i++){
 
        int candid2=INT_MAX,candid3=INT_MAX;
 
        if(i%2==0)candid2=DP[i/2]+1;
        if(i%3==0)candid3=DP[i/3]+1;
 
        DP[i]=DP[i-1]+1;
        (candid2>=candid3?candid3:candid2)>=DP[i]?DP[i]:DP[i]=candid2>=candid3?candid3:candid2;
    }
    std::cout<<DP[num];
    return 0;
}

 

삼항연산자를 사용해 가독성이 안좋은 점 양해부탁드린다;;;;

 

얼추 설명하자면 1일 때 답은 0, 2일 때 답은 1, 3일 때 답은 1이 되는데 이를 초기식으로 지정하고 4부터 해당숫자가 2로 나누어지면 그숫자에서 나누기 2한 답에서 +1을 시켜 변수에 저장하고 3으로도 나누어진다면 나누기 3한 답에서 +1이 될테니 각각 저장한 변수와 그전의 값(-1한 답)에 +1 한 것과 3개를 비교해 가장 작은 것을 채택하는 방법으로 구했다. 

 

여기서 vector의 초기화 방법을 사용하였으며  

초기값으로 int형의 최대값을 지정하기 위해 #include<limits.h> 함수의 INT_MAX를 사용하였다.