[C++]백준 알고리즘 1463번

풀이는 아래와 같다.

#include <iostream>
 
using namespace std;
 
 
int count[1000001];
void solve(int);
 
int min(int a, int b){
    return a>b? b:a;
}
 
int main(){
    int n;
    cin >> n;
    solve(n);
    
    cout << count[n] << '\n';
    return 0;
}
void solve(int n){
    for(int i=1; i<=n; i++){
        if(i == 1){
            count[i] = 0;
        }else if(i == 2 || i == 3){
            count[i] = 1;
        }else{
            count[i] = count[i-1]+1;
            if( i%3 == 0){
                count[i] = min(count[i/3]+1,count[i]);
            }if( i%2 == 0){
                count[i] = min(count[i/2]+1,count[i]);
            }
        }
    }
    return;
}

처음에는 그냥 3으로 나누는게 가장 1로 빨리 가는 방법일 거라고 생각해서 전혀 자세히 생각하지 않고 알고리즘을 짰었는데, 그 다음으로는 2로 나누고, 그다음은 1을 빼는게 제일 줄어드는 폭이 작지 않을까 생각했었다. 근데 자세히 생각해보니 반례가 많은 것이다.

예를 들어 10을 한번 보자. 처음 생각한 방법대로라면 10->5->4->2->1 로 총 연산이 4번 진행된다. 하지만 실제로는 10->9->3->1의 방법으로 3번이 최소 횟수이다. 이런 사고 과정을 통해 알고리즘을 다르게 짜야됨을 깨달았다. 그래서 여기서 사용하기로 한 방법은 DP인데 Bottom up 방식과 Top down 방식 중에서 Bottom up 방식을 이용하기로 했다. 사실 알고리즘 초보라서 동적 프로그래밍도 잘 모르는데, 이런 간단한 문제들을 계기로 조금씩 더 익혀야겠다는 생각이 들었다!!! 그렇게 과제들을 C++로 하면서 알고리즘 자체에 대해서는 별로 생각을 안 했다니,, 얼마나 과제로 낸 코드들이 비효율적이었을까,, 암튼 더 열심히 해보자! 오랜만에 글을 올리는 거 같다 ㅎㅎㅎ 앞으로 또 꾸준히 오겠습니다^~^

 

이 글을 읽을 사람이 있을진 모르겠지만,

나는 현재 군인이고 여기서 할 수 있는 공부 중 하나인 알고리즘 공부를 기록으로 남기기 위해 이 티스토리를 작성하고 있다. 백준 문제에 대한 풀이와 시행착오를 기록할 예정이니 누군가에게 도움이 되면 좋겠다.