[백준] #1463 1로 만들기

요즘은 DP 문제들을 연습하고 있다.

 

 

지난번에 푼 "#2839 설탕 배달" 문항이랑 비슷한 느낌인 문제이다.

그 느낌을 기억해서 풀려고 했는데, 처음 제출한 코드는 아래와 같다. (채점 결과 틀렸다.)

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

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

        int[] dp = new int[N + 1];
        dp[1] = 0;
        if (N >= 2) dp[2] = 1;
        if (N >= 3) dp[3] = 1;

        for (int i = 4; i <= N; i++) {
            dp[i] = 1000001; // 큰 값
            if (i % 2 != 0 && i % 3 != 0) {
                dp[i] = dp[i - 1] + 1;
                continue;
            }
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }

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

 

질문 게시판에서 아래와 같은 반례를 찾을 수 있었다.

N: 28

실제 답: 4 (28 -> 27 -> 9 -> 3 -> 1)

내 코드: 5 (28 -> 14 -> 7 -> 6 -> 2 -> 1)

 

반례를 보니까 머리가 아파졌고 생각해야 하는 경우의 수가 더 늘었다고 생각했다...

i-1 해서 3으로 나눠떨어지면 그것도 고려해야 하구나 그런 생각...

 

그래서 for문 안 쪽을 이런 식으로 작성해서 모든 경우의 수를 따졌다...

        for (int i = 4; i <= N; i++) {
            dp[i] = 1000001; // 큰 값

            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            } else {  // i % 2 != 0
                dp[i] = Math.min(dp[i], dp[i - 1] + 1);
            }

            if ((i - 2) % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i - 2] + 2);
            } else if ((i - 1) % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i - 1] + 1);
            } else {    // i % 3 == 0
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }

답은 맞았으나 불필요한게 너무 많은 코드다.

생각해보니 min 함수를 사용하고 있기 때문에 이렇게 하나하나 경우를 나눠 코드를 작성할 필요가 없다.

 

아래와 같이 간단히 작성 가능하다.

우선 연산의 수가 적어지려면 좋은 연산 순서는 "3으로 나누기 > 2로 나누기 > 1 빼기" 인데,

min 함수를 통해 최솟값이 대체될 수 있으니 결과적으로 아래와 같이 간결하게 작성 해주면 된다.

DP

import java.io.*;

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

        int[] dp = new int[N + 1];
        dp[1] = 0; 

        for (int i = 2; i <= N; i++) {
            // 기본: 1을 빼는 경우
            dp[i] = dp[i - 1] + 1;

            // 2로 나눌 수 있는 경우
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }
            // 3으로 나눌 수 있는 경우
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }

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

 

 

다른 풀이들을 보니 DFS나 BFS로도 풀 수 있음을 깨달았다. (시간 더 빠른 듯)

DFS

import java.io.*;
 
class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		System.out.print(recur(N, 0));
	}
 
	static int recur(int N, int count) {
		if (N < 2) {
			return count;
		}
		return Math.min(
        		recur(N / 2, count + 1 + (N % 2)), 
        		recur(N / 3, count + 1 + (N % 3))
    		);
    }
}

recur(N / 2, count + 1 + (N % 2)) 의 의미는?

• + 1: 나누기 연산 1번
• + (N % 2): 2로 나누어 떨어지지 않으면, 2로 나누기 전에 1을 빼는 연산을 해줘하므로 이 항이 들어간다.
• ex) N = 11 -> n % 2 = 1 -> 1을 빼는 연산 필요 -> count에 1을 더해준다.

recur(N / 3, count + 1 + (N % 3))의 의미는?

• + 1: 나누기 연산 1번
• + (N % 3): 3으로 나누어 떨어지지 않으면, 3로 나누기 전에 1을 빼는 연산을 1번 또는 2번 해줘하므로 이 항이 들어간다.
• ex) N = 10 -> n % 3 = 1 -> 1을 빼는 연산 필요 -> count에 1을 더해준다.
• N = 11 -> n % 3 = 2 -> 2을 빼는 연산 필요 -> count에 2을 더해준다.

 

BFS

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println(bfs(N));
    }

    static int bfs(int n) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[] visited = new boolean[n + 1];

        queue.add(new int[]{n, 0});
        visited[n] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int value = cur[0];
            int count = cur[1];

            if (value == 1) {
                return count;
            }

            if (value % 3 == 0 && !visited[value / 3]) {
                visited[value / 3] = true;
                queue.add(new int[]{value / 3, count + 1});
            }
            if (value % 2 == 0 && !visited[value / 2]) {
                visited[value / 2] = true;
                queue.add(new int[]{value / 2, count + 1});
            }
            if (value - 1 > 0 && !visited[value - 1]) {
                visited[value - 1] = true;
                queue.add(new int[]{value - 1, count + 1});
            }
        }

        return -1;
    }
}

visited는 왜 필요할까?

같은 숫자를 중복 탐색하지 않게 막는다. 만약 이미 방문한 숫자를 다시 방문하면, 어차피 같은 탐색이 실행되기 때문에 의미가 없음