[백준] 12852 1로 만들기 2 - Java

 

 

 

문제 출저 

https://www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

 

 

 

문제 풀이

숫자가 주어졌을 때, 3이나 2로 나누어 떨어지면 나눌 수 있고 -1을 할 수 있다. 이런 식으로 연산을 거쳐 1을 만들 때 최소한 연산 횟수와 그 과정을 구해야 합니다. 

 

 

DP를 이용해서 풀었습니다. 

처음에 BFS로 Queue를 이용하고 이미 방문한 곳이 횟수가 적으면 가지치기를 하는 방식으로 풀었는데 시간 초과가 발생했습니다. 

 

1차원 배열과 메모리제이션으로 코드를 바꿔서 문제를 풀었습니다. 

문제를 풀기 위해 dot 클래스를 새로 만들었습니다. dot 클래스는 횟수를 저장하는 count와 이 때 까지의 과정을 저장한 문자열 String history를 가지고 있습니다. 

target의 길이를 가진 1차원 dot 배열을 생성합니다.

그리고 2부터 target 까지 for문 연산을 수행합니다. 

각각의 위치에서 2로 나누어 떨어지는 3으로 나누어 떨어지는지 확인한 다음 각각의 경우를 했을 때 연산 횟수를 비교하고 가장 작은 것을 저장하여 정답을 구했습니다. 

 

 

 

소스 코드

package baekjoon.backjoon11.day0110.day08;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
1로 만들기 2
https://www.acmicpc.net/problem/12852

bfs를 활용해 Queue로 풀면 시간 초과가 발생한다.
배열과 메모리제이션으로 문제를 푼다.
 */
public class B12852 {



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

    dot[] dp = new dot[target+1];
    dp[1] = new dot(0, "1");

    for(int i = 2; i < target+1; i++) {

      int selectCount = Integer.MAX_VALUE;
      String selectHistory = "";

      if(i % 3 == 0) {
        selectCount = dp[i/3].count + 1;
        selectHistory = i + " " + dp[i/3].history;
      }

      if(i % 2 == 0) {
        if(selectCount > dp[i/2].count + 1) {
          selectCount = dp[i/2].count + 1;
          selectHistory = i + " " + dp[i/2].history;
        }
      }

      if(selectCount > dp[i-1].count + 1) {
        selectCount = dp[i-1].count + 1;
        selectHistory = i + " " + dp[i - 1].history;
      }

      dp[i] = new dot(selectCount, selectHistory);
    }

    System.out.println(dp[target].count);
    System.out.println(dp[target].history);

  }

  public static class dot {
    int count;
    String history;

    dot(int count, String history) {
      this.count = count;
      this.history = history;
    }
  }


}