[BOJ] 1463 1로 만들기 - JAVA

1. 문제

1463번: 1로 만들기

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

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

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

---

2. 풀이

DP

• N+1배열을 만든다.(숫자로 접근하기때문에 그냥 메모리 한 칸 더 쓰는게 낫다. 매번 계산하는게 더 시간드니까)
• -1에서 접근한 값, /2에서 접근한 값, /3에서 접근한 값을 전부 비교해서 그중에 가장 작은 값을 선택한다.
• 주석보면 나는 +1을 마지막으로 해줬는데 그러면 배열을 최소 2번에서 최대 6번까지 접근하게 된다. 하지만 비교할때부터 +1해가면서 저장하면 배열접근횟수를 1번~5번으로 줄일 수 있다. 

import java.io.*;

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

      int[] counts = new int[N + 1];

      for (int i = 2; i <= N; i++) {
         counts[i] = counts[i - 1]+1;
         if (i % 3 == 0) counts[i] = Math.min(counts[i / 3]+1, counts[i]);
         if (i % 2 == 0) counts[i] = Math.min(counts[i / 2]+1, counts[i]);
//       ++counts[i];   //마지막에 +1하는것보다 비교할 때 +1하는게 시간이 더 적게든다. 배열 접근시간을 생각하자!!
      }

      System.out.println(counts[N]);
   }
}

 

DFS

• 입력받은 n과 몇 번째에 도달했는지 depth를 파라미터로 가지고 다녀야 한다. 
• 중간에 depth가 최솟값을 저장한 result보다 크거나 같게 되면 바로 함수를 끝낸다.
• n이 1보다 작아져도 끝낸다.
• n이 1에 도달하면 result에 depth를 저장한다. (앞부분에서 result보다 큰 depth를 미리 걸러내서 가능)
• 재귀를 부를때는 n을 빨리 줄일수 있는 방향으로 가야한다. 그러니까 /2 -> /3 -> -1 순이다. 이 순서가 아니면 시간초과난다.

static int result = Integer.MAX_VALUE;

//main
dfs(N,0);
System.out.println(result);

//dfs
private static void dfs(int n, int depth) {
   if(depth >= result || n < 1) return;
   else if(n==1) {
      result = depth;
      return;
   }
   if(n%2==0) dfs(n/2,depth+1);
   if(n%3==0) dfs(n/3,depth+1);
   dfs(n-1,depth+1);
}

BFS

• dfs와 마찬가지로 먼저 n이 작아지는 순서대로 queue에 담는다. /2 -> /3 -> -1 순이다.
• 만약 뽑아낸 n이 1이라면 반복을 종료한다.
• top down방식이므로 visited[1]을 반환한다.

//main
System.out.println(bfs(n));

//bfs
private static int bfs(int n){
   int[] visited = new int[n+1];

   Queue<Integer> queue = new ArrayDeque<>();
   queue.offer(n);
   visited[n] = 0;
   while(!queue.isEmpty()){
      n = queue.poll();
      if(n==1) break;

      if(n%2==0 && visited[n/2]==0) {
         queue.offer(n/2);
         visited[n/2] = visited[n]+1;
      }
      if(n%3==0 && visited[n/3]==0) {
         queue.offer(n/3);
         visited[n/3]=visited[n]+1;
      }
      if(n>1 && visited[n-1]==0) {
         queue.offer(n-1);
         visited[n-1]=visited[n]+1;
      }
   }

   return visited[1];
}

---

3. 결과

앞의 한 번은 배열 크기 때문에 틀렸다. 배열 크기를 N+1안하고 메모리를 아껴보려고 하다가 중간에 배열접근할 때 매번 -1해야하는 걸 잊었다.

다음으로 /2와 /3 값만 비교해서 틀렸다. (-1값도 비교해야한다.)

---

추가 : DFS, BFS 방식으로 풀어봤다.

dfs로 풀 때 가지치기를 덜해서 시간초과가 났다.

1) depth로 가지치기해주고,

2) 재귀 호출 순서를 변경

했더니 맞았다.

bfs는 여기서도 걸리는 시간이 엄청 짧다. 메모리와 시간을 맞바꿨다.