[코드트리/NOVICE MID] 4가지 연산을 이용하여 1 만들기 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• 다익스트라 (397ms, 29MB)

연산횟수를 저장하는 1차원 int형 배열을 생성해 초기값을 큰 값으로 저장해두고, 시작점 N은 거리를 0으로 설정한다.

 

연산횟수가 적은 순으로 오름차순 정렬하는 우선순위 큐에 4가지 경우(현재 숫자에서 1을 뺀 경우, 1을 더한 경우, 2로 나눠 떨어질 경우 2로 나눈 경우, 3으로 나눠 떨어질 경우 3으로 나눈 경우)를 추가한다. 그리고 이동했을 때의 연산횟수와 현재 위치에서 1초 지난 값을 비교해  연산횟수 배열을 둘 중 더 값이 작은 값으로 갱신한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int MAX = 1_000_000;
 
    static int N;
    static int[] cntArr = new int[MAX + 1];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
 
        Arrays.fill(cntArr, MAX);
 
        bfs();
        System.out.println(cntArr[1]);
    }
 
    private static void bfs() {
        cntArr[N] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(N, 0));
 
        while(!pq.isEmpty()) {
            Node cur = pq.poll();
 
            int n1 = cur.num - 1;
            if(inRange(n1) && cntArr[n1] > cur.cnt + 1) {
                cntArr[n1] = cur.cnt + 1;
                pq.add(new Node(n1, cntArr[n1]));
            }
            
            int n2 = cur.num + 1;
            if(inRange(n2) && cntArr[n2] > cur.cnt + 1) {
                cntArr[n2] = cur.cnt + 1;
                pq.add(new Node(n2, cntArr[n2]));
            }
 
            if(cur.num % 2 == 0) {
                int n3 = cur.num / 2;
                if(inRange(n3) && cntArr[n3] > cur.cnt + 1) {
                    cntArr[n3] = cur.cnt + 1;
                    pq.add(new Node(n3, cntArr[n3]));
                }
            }
            
            if(cur.num % 3 == 0) {
                int n4 = cur.num / 3;
                if(inRange(n4) && cntArr[n4] > cur.cnt + 1) {
                    cntArr[n4] = cur.cnt + 1;
                    pq.add(new Node(n4, cntArr[n4]));
                }
            }         
        }
    }
 
    private static boolean inRange(int num) {
        return (1 <= num && num <= MAX);
    }
}
 
class Node implements Comparable<Node> {
    int num, cnt;
 
    public Node(int num, int cnt) {
        this.num = num;
        this.cnt = cnt;
    }
 
    @Override
    public int compareTo(Node n) {
        return this.cnt - n.cnt;
    }
}

 

 

➕ 다른 풀이 방식

단순 BFS로도 풀 수 있다. (117ms, 9MB)

import java.util.*;
import java.io.*;
 
public class Main {
    static final int MAX = 1_000_000;
    
    static int n;
    static boolean[] visited = new boolean[MAX + 1];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        System.out.print(bfs());
    }
    static int bfs(){
        int ans = 0;
 
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{n, 0});
 
        visited[n] = true;
        
        while(!q.isEmpty()){
            int[] now = q.poll();
            int val = now[0];
            int cnt = now[1];
            
            if(val == 1){
                ans = cnt;
                break;
            }
            
            if(inRange(val - 1) && !visited[val - 1]){
                visited[val-1] = true;
                q.add(new int[]{val - 1, cnt + 1});
            }
            
            if(inRange(val + 1) && !visited[val + 1]){
                visited[val + 1] = true;
                q.add(new int[]{val + 1, cnt + 1});
            }
            
            if(inRange(val) && val % 2 == 0 && !visited[val / 2]){
                visited[val / 2] = true;
                q.add(new int[]{val / 2, cnt + 1});
            }
            
            if(inRange(val) && val % 3 == 0 && !visited[val/3]){
                visited[val / 3] = true;
                q.add(new int[]{val / 3, cnt + 1});
            }
        }
        
        return ans;
    }
    
    private static boolean inRange(int num) {
        return (1 <= num && num <= MAX);
    }
}

---

💦 어려웠던 점

X. 며칠 전 백준 숨바꼭질 3 문제랑 비슷해서 쉽게 풀 수 있었다.

 

 

🧐 새로 알게 된 내용

최소 연산 횟수 계산 = 각 연산의 가중치는 1이므로 가중치가 전부 1인 그래프가 있을 때 정점 n~1까지의 최단거리 계산 문제 ▷ BFS로 해결 가능

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 비슷한 문제 : 백준 13549 숨바꼭질3

[백준/JAVA] 13549번: 숨바꼭질 3