[Python][C++] 1463번 1로 만들기

문제

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

 

 

 

 

코드

1. Python

n = int(input())

dp = [0] * (n+1)

for i in range(2, n + 1):
    dp[i] = dp[i-1] + 1
    
    if i % 3 == 0:
        dp[i] = min(dp[i//3] + 1, dp[i])
    if i % 2 == 0:
        dp[i] = min(dp[i//2] + 1, dp[i])

print(dp[n])

 

2. C++

   1. DP

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    vector<int> dp(n + 1, 0); // dp[i]는 i를 1로 만드는 최소 연산 횟수

    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로 나누는 연산
        if (i % 3 == 0)
            dp[i] = min(dp[i], dp[i / 3] + 1); // 3으로 나누는 연산
    }

    cout << dp[n] << endl;
    
    return 0;
}

 

   2. BFS

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// BFS 함수: 주어진 숫자 x를 1로 만들기 위한 최소 연산 횟수를 반환
int bfs(int x) {
    vector<int> visited(1000001, -1); // 방문 여부 및 연산 횟수를 저장할 벡터, -1로 초기화
    queue<int> q; // BFS 수행을 위한 큐

    q.push(x); // 시작 노드를 큐에 삽입
    visited[x] = 0; // 시작 노드의 연산 횟수를 0으로 설정

    // 큐가 비어있지 않는 동안 반복
    while (!q.empty()) {
        x = q.front(); // 큐의 앞쪽 요소를 가져옴
        q.pop(); // 큐에서 제거

        // 목표인 1에 도달하면 연산 횟수 반환
        if (x == 1)
            return visited[1];

        // 3으로 나누어 떨어지고, 아직 방문하지 않은 경우
        if (!(x % 3) && visited[x / 3] == -1) {
            q.push(x / 3); // 큐에 삽입
            visited[x / 3] = visited[x] + 1; // 연산 횟수 갱신
        }
        
        // 2로 나누어 떨어지고, 아직 방문하지 않은 경우
        if (!(x % 2) && visited[x / 2] == -1) {
            q.push(x / 2); // 큐에 삽입
            visited[x / 2] = visited[x] + 1; // 연산 횟수 갱신
        }

        // 1을 빼는 경우
        if (visited[x - 1] == -1) {
            q.push(x - 1); // 큐에 삽입
            visited[x - 1] = visited[x] + 1; // 연산 횟수 갱신
        }
    }
}

int main() {
    int n;

    cin >> n;

    cout << bfs(n);

    return 0;
}

 

 

풀이 

BFS나 DP로 해결이 가능한데, 백준 결과는 BFS가 더 빠르고 지피티는 DP가 더 효율적이라고 한다.

BFS가 더 효율적이라고 생각해서 지피티랑 논의하다가 이해하기를 포기했다... 아무리 생각해도 BFS가 더 효율적인 것 같다.

 

DP풀이는 다른 블로그에도 많기 때문에 BFS 풀이만 설명함

 

어떤 정수 x에서 갈 수 있는 결과값 x / 3, x / 2, x - 1 세 정수를 x와 단방향으로 연결된 그래프라고 생각하고 BFS를 하면 된다. 예를 들어 x가 6이면 graph[6] = {2, 3, 5} 가 됨. 

 

 

1. 벡터 초기화:
   • visited 벡터는 -1로 초기화하여 방문 여부와 연산 횟수를 동시에 관리
2. BFS 반복:
   • 각 상태에서 가능한 모든 연산(3으로 나누기, 2로 나누기, 1 빼기)을 큐에 추가
3. 연산 수행 및 방문 체크:
   • 각 연산을 수행할 때, 이미 방문한 적이 없는 경우에만 큐에 추가하고 연산 횟수를 갱신합니다.
4. 종료 및 출력:
   
   • 현재 값이 1이면 해당 위치의 연산 횟수를 반환

 

 

BFS 참고

https://ehdbs0903.tistory.com/entry/Algorithm-너비-우선-탐색-BFSBreadth-First-Search-알고리즘

[Algorithm] 너비 우선 탐색 / BFS(Breadth-First Search) 알고리즘