백준, BOJ, 1463번 C++ [CPP]

흠... 나는 처음에 BFS로 풀었는데 사람들이 DP라고 한다..

그래서 둘다 풀어보았다.

시간제한이 아주 짧은 것으로 보아... 그렇다. DP가 확실하였구나

1초에 5억번 연산이라치면.. 1/6 대충 8천만번이면 되겠구나.

 

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

1463번: 1로 만들기

 

---

 

먼저 BFS로 한 풀이

15분만에 푼 것 같다.

#include<iostream>
#include<queue>
using namespace std;
int num[1000001];
int dist[1000001];
queue<int> Q;
int target;
void init() {
    ios::sync_with_stdio(0);
    cin.tie(0);
}
int main() {
    init();
    cin >> target;
    Q.push(target);
    num[target] = 1;
    while (!Q.empty()) {
        int cur = Q.front();
        Q.pop();
		//3종류의 연산
        for (int i = 0; i < 3; i++) {
            int nx;
            // 3 나누기
            if (i == 0) {
                if (cur % 3 != 0) continue;
                nx = cur/3;
            }
            // 2 나누기
            if (i == 1) {
                if (cur % 2 != 0) continue;
                nx = cur/2;
            }
            // 1 빼기
            if (i == 2) {
                nx = cur-1;
            }
            //범위 체크
            if (nx <= 0) continue;
            //방문체크 -> 이미 방문했다면 그 숫자에 도달하는 더 빠른 길이 있다는 소리 -> 즉, 방문했을 경우 넘어감
            if ( num[nx] != 0) continue;
            dist[nx] = dist[cur] + 1; // 거리표시
            num[nx] = 1; // 방문 표시
            Q.push(nx);
            //if (dist[1]) break;
        }
        //하지만 시간복잡도를 위해 다 조사를 할 순 없으므로 1에 방문하면 종료
        if (dist[1]) break;
    }
    cout << dist[1];
}

 

 

다음은 DP로 푼 문제

 

중간에 while은 for로 돌려도 좋다.

#include<iostream>

using namespace std;

int num[1000001];

int main(){
    int n;
    cin >> n;

    // 미리 범위에 있는 값 모두 계산하고 풀 수 있음
    // 예를 들어 100에서 최소연산을 구하려고 해보자. 
    // 당연히 2로 나누어 50을 구할 것이다.
    // 그렇다면 50에서 최소연산을 구하는 문제로 바뀐다.
    // 다시 25가 된다면 25에서 최소연산을 구하는 문제로 바뀐다. 
    // 피보나치 수열과 비슷한 느낌이라 생각하면 된다.
    int i = 1;
    while( ++i < 1000001){
        //i = 2일 때 num[2] == 1 이라는 이야기.
        num[i] = num[i-1]+1;
        
        //1을 도달하는데 2로 나누는 것이 더 빠르면.
        if(i%2 == 0){
            if(num[i] >= num[i/2]+1) {
                num[i] = num[i/2]+1;
            }
            
        }
        
        //1을 도달하는데 3으로 나누는 것이 더 빠르면.
        if(i%3 == 0){
            if(num[i] >= num[i/3]+1){
                num[i] = num[i/3]+1;
            }
        }
    }

    cout << num[n];
}