백준 1463번 - 1로 만들기(JAVA)

해당 문제를 풀면서 고민했던 과정들을 정리해봤다 ੭ ᐕ)੭

 

 

자 이번 문제는 (1)3으로 나누기 (2)2로 나누기 (3)1빼기

3가지 방법을 써서 가장 적은 횟수로 1을 만드는 경우의 최솟값를 출력하는 것이다

문제를 이해하기 쉽게 10을 1로 만드는 경우 과정을 그려보면 아래와 같다

 

3이나 2로 나누고 1로 빼면서 1이 만들어지면 멈춘다

 

구현은 큐를 이용해서 10을 넣고 꺼내면서 10/3 10/2 10-1 한 값을 큐에 넣고

다시 그 값을 꺼내면서 a/3 a/2 a-1 한 값을 큐에 넣는 과정을 반복할 것이다

여기서 생각해야 할 것은

(1) 꺼낸 값이 1이 되면 반복을 멈춘다

(2) 위의 3과 4처럼 이미 거쳐간 숫자는 다시 연산할 필요가 없으므로 visited 배열을 만들어서

사용한 수는 큐에 넣지 않고 넘어간다

(3) 몇 번 연산을 했는지 기록해야 하므로 -5를 넣어서 각 라운드를 구분한다

-5가 사용되는 방법은 다음 그림과 같다

처음에 10을 큐에 넣을 때 -5를 같이 넣어서

꺼낸 값이 -5일 경우 한 라운드를 다 돈 것으므로 다시 큐로 넣는다

그리고 count 값을 증가시킨다

 

이를 코드로 나타내면 다음과 같다

static LinkedList<Integer> queue = new LinkedList<>();
static int[] method = {3, 2};
static int count = 0;

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());

// n값이 10일 경우 visited 크기가 10이라면 visited[10]으로 접근하면 Exception이 발생하므로 +1을 해준다
    boolean[] visited = new boolean[n+1];
    BFS(n, visited);

    System.out.print(count);
}

static void BFS(int node, boolean[] visited){

    queue.add(node);
    queue.add(-5);
    visited[node] = true;

    while(!queue.isEmpty()){

        int now = queue.poll();

        // -5가 나온경우 다시 값을 꺼내고 count를 증가시킨다
        if(now == -5){
            now = queue.poll();
            count++;
            queue.add(-5);
        }

        // 1이 나오면 멈춘다
        if(now == 1){
            return;
        }

        // 3, 2로 나눌때
        for(int i=0; i<2; i++){
            if(now % method[i] == 0){
                int num = now / method[i];
                if(!visited[num]){
                    queue.add(num);
                    visited[num] = true;
                }
            }
        }
        // -1 일 때
        if(now > 1 && !visited[now-1]){
            queue.add(now-1);
            visited[now-1] = true;
        }

    }

}