백준 1463 1로 만들기 c++ [컴공과고씨]

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

1463번: 1로 만들기

이 문제를 보고 bfs로 탐색을 하여 풀면 쉽게 풀릴거라고 생각해서 bfs로 풀어주었다.

풀고 난 후 힌트 부분쪽에는 다이나믹 프로그래밍이라고 되어있어서 다이나믹 프로그래밍으로도 풀고

두 개 방식 모두 정리해보았다.

 

첫번째 방식은 bfs로 푼 방식으로 처음에 딱 떠올라서 푼 방식이다.

입력 받은 n을 bfs에 넣어주면 bfs는

- 3으로 나눠지고 나눈수가 방문되어지지 않은 경우 큐에 넣어준다.

- 2로 나눠지고 나눈수가 방문되어지지 않은 경우 큐에 넣어준다.

- 1을 뺀 수가 방문되어지지 않은 경우 큐에 넣어준다.

그 후 1을 방문했을 경우 카운팅한 값을 ans에 저장해주고 출력하면 된다.

 

bfs 전체코드

#include <iostream>
#include <queue>
using namespace std;
long long n;
bool visit[1000001];
int cnt = 0;
int ans = 0;
void bfs(int x){
    queue<pair<long long, int>> q; 
    q.push(make_pair(x, 0));
    visit[x] = true;
    while(!q.empty()){
        int a = q.front().first;
        cnt = q.front().second;
        q.pop();
        if(a == 1){ // 목표 수 1되면 종료
            ans = cnt;
            break;
        }
        if(a % 3 == 0 && !visit[a/3]){ 
            // 3으로 나눠지고 나눈수가 방문되어지지 않은 경우
            q.push(make_pair(a/3, cnt+1));
            visit[a / 3] = true;
        }
        if(a%2 ==0 && !visit[a/2]){
            // 2로 나누어지고 나눈 수가 방문되어지지 않은 경우
            q.push(make_pair(a/2, cnt+1));
            visit[a / 2] = true;
        }
        if(!visit[a-1]){
            //1을 뺀 수를 방문되어지지 않은 경우
            q.push(make_pair(a-1, cnt+1));
            visit[a - 1] = true;
        }
        
    }
} // bfs
int main(){
    cin >> n;
    bfs(n);
    cout << ans;
    return 0;
}

사용 알고리즘 bfs

 

 

두번째 방법은 다이나믹 프로그래밍을 이용한 방법이다.

이것은 거꾸로 1에서 시작해서 n까지 도달했을 때 카운팅 된 수를 출력해주면된다.

#include <iostream>
using namespace std;
int re_min(int x, int y){
    return (x < y ? x : y);
    //삼항 연산자 사용
    //x가 작을 경우 x 반환 y가 작을경우 y반환
}
int main(){
    int N;
    cin >> N;
    int dp[1000001];
    dp[1] = 0;
 
    for (int i = 2; i <= N; i++){
        dp[i] = dp[i - 1] + 1; // -1 한 수에 +1
        if(i%2==0){
            dp[i] = re_min(dp[i], dp[i / 2] + 1);
            //현재있는 수와 2를 나눈 수에서 온 수를 비교
        }
        if(i%3==0){
            dp[i] = re_min(dp[i], dp[i / 3] + 1);
            //현재있는 수와 3를 나눈 수에서 온 수를 비교
        }
    }
    cout << dp[N];
}

사용 알고리즘 : 다이나믹 프로그래밍(dynamic programming)

 

yea!