[BOJ] 백준 1463번 : 1로 만들기 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

풀이

알고리즘 분류는 다이나믹 프로그래밍이지만, BFS를 통한 완전탐색으로도 풀 수 있는 문제였습니다. 전반적인 로직은 아래와 같습니다.

1. 숫자와 연산하는 횟수를 저장하는 클래스를 만든다. (num과 cnt를 클래스 변수로 설정.)

2. 맨 처음 입력받은 숫자와 0을 위에서 제작한 클래스의 객체로 만들어서 큐에 offer한다. 

3. 큐에서 poll해서 요소(X라 지칭)를 하나 꺼내고, 그 요소에 대해 아래 조건이 만족하는지 확인한다. (3-1 ~ 3-3은 독립된 조건임.)

3-1. X.num이 3으로 나누어 떨어지면, (X.num / 3, X.cnt + 1)을 큐에 offer한다.

3-2. X.num이 2로 나누어 떨어지면, (X.num / 2, X.cnt + 1)을 큐에 offer한다.

3-3. (X.num - 1, X.cnt + 1)을 큐에 offer한다.

4. 큐에 poll한 요소의 num이 1이라면, cnt를 반환하고 종료한다.

 

로직 자체는 단순한데, 중복된 값을 visited로 처리를 해 주어야 무한 루프를 해결할 수 있다는 점에 유의하시면 되겠습니다.

아래는 위 과정을 정리한 소스코드입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
 
class Number {
    int num;
    int cnt;
 
    Number(int num, int cnt) {
        this.num = num;
        this.cnt = cnt;
    }
}
 
public class Main {
    static int ans = 0;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
 
        BFS(N);
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    public static void BFS(int N) {
        Queue<Number> q = new LinkedList<>();
        boolean[] visited = new boolean[1000001];
        q.offer(new Number(N, 0));
        visited[N] = true;
 
        while (!q.isEmpty()) {
            Number n = q.poll();
 
            if (n.num == 1) {
                ans = n.cnt;
                break;
            }
 
            if (!visited[n.num / 3] && n.num % 3 == 0) {
                visited[n.num / 3] = true;
                q.offer(new Number(n.num / 3, n.cnt + 1));
            }
 
            if (!visited[n.num / 2] && n.num % 2 == 0) {
                visited[n.num / 2] = true;
                q.offer(new Number(n.num / 2, n.cnt + 1));
            }
 
            if (n.num - 1 >= 0 && !visited[n.num - 1]) {
                visited[n.num - 1] = true;
                q.offer(new Number(n.num - 1, n.cnt + 1));
            }
        }
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.