자바(백준) 12852 1로 만들기 2

오답 노트 & 새로 알게 된 점

문제를 풀면서 처음에는 메모리 초과, 다음에는 시간 초과가 났다. 그래서 도저히 어떻게 풀지 감이 안 와서 구글링을 통하여 문제를 해결했다. 

 

카테고리를 보니 DP와 BFS로 되어있었다. DP는 어떻게 사용되는지 보였다. 그러나 엥? BFS는 어디있는거지라는 생각을 했다. 아마 문제를 풀 때 최소를 구하기 위한 탐색 방법 중 하나인 BFS 모양(?)과 비슷하여 분류가 그렇게 된 건가 싶었다. 나는 BFS를 생각하면 BFS == 큐라고 생각하고 있었기 때문이다. 그런데 이 문제를 보면서 꼭 큐를 사용해야만 BFS 다는 아닌가 보다 라는 생각이 들었다.

 

난 DP를 제대로 공부하지 않고, 단지 메모이제이션(?) 그 부분만 알고 있다. 전에 했던 것을 저장하여 앞으로 나아가는 것이라고 대강 알고 있다.

 

그래서 dp배열을 보면 해당 숫자까지 오는데 횟수와, 해당 숫자가 2 또는 3으로 나뉠 경우에 나뉜 index의 횟수에서 + 1을 비교하고, 그중 작은 수를 해당 dp배열의 index에 저장한다. 그래서 dp[N]은 N까지 도달하는데 최소 횟수를 저장하게 된다.

 

before배열은 경로를 저장하는 것이다. 즉, 해당 배열의 값은 그 전의 거쳤던 경로(index)를 나타나게 된다.

예로 10을 생각해보자.

처음에 10을 str에 저장한다.

before[10] = 9이다. 그래서 이것은 전에 갔었던 곳의 index를 가리킨다. 그 index의 value는 또 그 전의 index를 나타낸다. 

지금은 str에 10 9가 저장

before[9] = 3

str = 10 9 3

before[3] = 1

str = 10 9 3 1

before[1] = 0으로 반복문 종료

 

---

 

코드

package DFS;
 
//BOJ 12852 1로 만들기 2
 
import java.util.*;
 
public class BOJ12852 {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
 
        ////////////////////////입력 끝
 
        int dp[] = new int[N + 1]; //최소 횟수 저장
        int before[] = new int[N + 1]; //경로 저장
 
        String str = "";
 
        dp[1] = 0;
 
        for(int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1;
            before[i] = i - 1;
 
            if (i % 3 == 0 && dp[i / 3] + 1 < dp[i]) {
                dp[i] = dp[i / 3] + 1;
                before[i] = i / 3;
            }
            if (i % 2 == 0 && dp[i / 2] + 1 < dp[i]) {
                dp[i] = dp[i / 2] + 1;
                before[i] = i / 2;
            }
        }
        System.out.println(dp[N]);
 
        while(N > 0){
            str += N + " ";
            N = before[N];
        }
 
        System.out.print(str);
 
    }
}