[BOJ] 12852 1로 만들기 2 - JAVA

1. 문제

12852번: 1로 만들기 2

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

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

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

---

2. 풀이

Bottom-up(dp)

1.  N에서 1로 만드는 경우의 수를 dp에 저장한다.

  -    dp[i]를 먼저 dp[i-1]+1로 저장한 뒤, dp[i/2]+1,dp[i/3]+1과 비교해서 더 작은 값이 있다면 교체한다.

2.  dp[N]부터 시작해서 dp[N]-1값과 같은 숫자를 찾아 StringBuilder에 더한다.

import java.io.*;
import java.util.*;

public class BOJ_12852_1로만들기2 {
   public static void main(String[] args) throws IOException {
      int N = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());

      int[] dp = new int[N+1];
      dp[1] = 0;
      for(int i=2;i<=N;i++){
         dp[i] = dp[i-1]+1;
         if(i%3==0) dp[i] = Math.min(dp[i], dp[i/3]+1);
         if(i%2==0) dp[i] = Math.min(dp[i], dp[i/2]+1);
      }

      StringBuilder sb = new StringBuilder();
      sb.append(dp[N]).append('\n').append(N).append(' ');
      int num = N;
      while(num!=1){
         if(num%3==0 && dp[num/3]==dp[num]-1) num = num/3;
         else if(num%2==0 && dp[num/2]==dp[num]-1) num = num/2;
         else num = num-1;
         sb.append(num).append(' ');
      }

      System.out.print(sb);
   }
}

 

Top-down(bfs)

BFS를 같이 활용해서 dp에 저장한다. queue에 N을 넣고 하나씩 뽑아서 탐색한다. N부터 시작해서 1까지 탐색하기 때문에 dp[1]이 연산을 사용하는 횟수의 최솟값이다.

int[] dp = new int[N+1];
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(N);
int num;
while(!queue.isEmpty()){
   num = queue.poll();
   if(num<=1) break;
   if(num%3==0 && dp[num/3]==0){
      queue.offer(num/3);
      dp[num/3] = dp[num]+1;
   }
   if(num%2==0 && dp[num/2]==0){
      queue.offer(num/2);
      dp[num/2] = dp[num]+1;
   }
   if(dp[num-1]==0){
      queue.offer(num-1);
      dp[num-1] = dp[num]+1;
   }
}

 

dp가 채워졌다면 N->1로 가는 경로를 출력하기 위해 answer배열을 채워야 한다. dp[1]+1사이즈의 배열을 만들어서 경로를 저장한다. 이때 N부터 시작하기 위해 dp[1]-1부터 0 순서로 채운다.

dp[num]-1이 dp[새로운 숫자]와 같다면 이동할 수 있다. num을 교체한다.

마지막에 answer[i]에 num을 저장하고 다음 반복 스텝을 돌린다.

//숫자 채우기
int[] answer = new int[dp[1]+1];
num = 1;
answer[dp[1]] = 1;
for(int i=dp[1]-1;i>=0;i--){
   if(num*3<=N && dp[num*3]==dp[num]-1) num*=3;
   else if(num*2<=N && dp[num*2]==dp[num]-1) num*=2;
   else num+=1;
   answer[i] = num;
}

 

StringBuilder을 이용해서 dp[1]과 answer배열을 출력한다.

//출력
StringBuilder sb = new StringBuilder();
sb.append(dp[1]).append('\n');
for(int n:answer) sb.append(n).append(' ');

System.out.println(sb);

 

전체 코드는 다음과 같다.

import java.io.*;
import java.util.*;

public class BOJ_12852_1로만들기2_2 {
   public static void main(String[] args) throws IOException {
      int N = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());

      int[] dp = new int[N+1];
      Queue<Integer> queue = new ArrayDeque<>();
      queue.offer(N);
      int num;
      while(!queue.isEmpty()){
         num = queue.poll();
         if(num<=1) break;
         if(num%3==0 && dp[num/3]==0){
            queue.offer(num/3);
            dp[num/3] = dp[num]+1;
         }
         if(num%2==0 && dp[num/2]==0){
            queue.offer(num/2);
            dp[num/2] = dp[num]+1;
         }
         if(dp[num-1]==0){
            queue.offer(num-1);
            dp[num-1] = dp[num]+1;
         }
      }

      //숫자 채우기
      int[] answer = new int[dp[1]+1];
      num = 1;
      answer[dp[1]] = 1;
      for(int i=dp[1]-1;i>=0;i--){
         if(num*3<=N && dp[num*3]==dp[num]-1) num*=3;
         else if(num*2<=N && dp[num*2]==dp[num]-1) num*=2;
         else num+=1;
         answer[i] = num;
      }

      //출력
      StringBuilder sb = new StringBuilder();
      sb.append(dp[1]).append('\n');
      for(int n:answer) sb.append(n).append(' ');

      System.out.println(sb);
   }
}

---

3. 결과

위가 bottom-up, 아래가 top-down방식이다.