[백준] 1463번: 1로 만들기 - Java, 자바

문제접근

이번에는 bottom-up방식으로 문제를 풀어보자.
bottom-up방식으로 문제를 풀 때는 아래서부터 어떠한 방식으로 dp배열을 채워나갈 것인가에 생각을 하게 된다. 1부터 차근차근 채워나가보자.
이 문제에서는 3가지 경우의 수를 갖고 있는데
1. x가 3으로 나누어 떨어지면 3으로 나눈다.
2. x가 2로 나누어 떨어지면 2로 나눈다.
3. 1을 뺀다.

이제부터 채워나갈 dp 배열은 값 N에 대하여 2 또는 3으로 나누어 떨어지면(N % 3 or 2 = 0;) 해당 값 중 가장 작은 값을 dp배열에 채워넣을 것이다. 1을 빼는 것은 모든 수에
적용한다.

• dp[1] = 0;

  • 1을 만드는 것에 대해 답이 0 이란 것엔 이변이 없다. 이 문제는 1을 만드는 문제인데 이미 1이기 때문이다.

• dp[2] = 1;

  • N = 2는 2로 나누어 몫이 1 나머지가 0 이된다. 따라서 N(2) / 2 = 1;
    • dp[2] = 1;
  • N = 2일 때 1을 빼면 1을 만들 수 있다.
    • dp[2] = 1;
  • 두 수를 비교하여 더 작은 수를 dp[2]에 대입한다.

• dp[3] = 1;

  • N = 3 일때 3으로 나누면 몫이1 나머지 0 이 된다. 따라서 N(3) / 3 = 1;
    • dp[3] = 1;
  • N = 3 일 때는 1을 빼면 2를 만들 수 있다. N (3) - 1 = 2;
    • 2에서는 다시 -1 을 빼면 1을 만들 수 있지만 그렇게 계산하는 것이 아닌,
    • N = 2상태에서 최솟값을 대입한 dp[2]를 더하는 것이다.
    • 다시말해, N = 3 일때, -1이라는 연산을 한번하고,
    • 3에서 1을 뺀 N = 2일 때의 최솟값인 dp[2]를 더해준다는 것이다.
    • 식으로 나타낸다면
    • dp[3] = dp[2] + 1 = 2; 이 된다.
      • +1 은 연산에 대하여 +1을 하는 것이다. 여기서는 나누기3을 한 연산숫자를 더한 것이다.
  • 두 수를 비교하여 더 작은 수를 dp[3]에 대입한다.

• dp[4] = 2;

  • N = 4 일때 2로 나누면 나머지가 0이되어 나누어떨어지고 몫이 2가 된다.
    • 몫2를 다시 2로 나누면 원하는 1이 나오게 된다.
    • 몫2를 2로 나누는것은 N = 2일때 선택할 수 있는 최솟값을 한것과 동일하고
    • 처음 N = 4 를 2로 나눈것은 연산 1번을 한 것이기 때문에 이것을 식으로 나타내면
    • dp[4] = dp[2] + 1; 이된다. 조금 더 상세히 보자면
    • dp[4] = dp[4/2] + 1; 이 된다.
      • 여기서도 +1은 연산한 숫자를 나타낸다 (나누기 2)
  • N = 4일 때 -1을 하는 연산을 하게되면 N = 3 이 되고, 3에서 최솟값을 구했던 dp[3]을
    • 더해주면 -1연산을할 때의 최솟값을 구할 수 있다.
    • dp[4] = dp[3] + 1;

• dp[5] = 3;

  • N = 5 일때는 3으로도 2로도 나누어서 나머지가0이 되지 않는다. 즉, 나누어 떨어지지 않는다.
  • 그렇다면 할 수 있는것은 -1 연산을 하는 것이다.
  • -1연산을 할경우는 N = 4를 만드는 것이고, N = 4 에 대한 연산의 최솟값은 dp[4]에 저장되어 있다.
  • dp[5] = dp[4] + 1;

• dp[6] = 3;

  • N = 6 일때는 3으로도 2로도 나누어 떨어진다 (나머지 0)
  • 그렇다면 이중에서 최솟값을 나타내는 값을 대입해주면 된다.
  • 2로 나누었을 때는 dp[6] = dp[6 / 2 = (3)] + 1;
    • dp[6] = 2;
  • 3으로 나누었을 때는 dp[6] = dp[6 / 3 = (2)] + 1;
    • dp[6] = 2;
  • 마지막으로 -1을 했을 때는
    • dp[6] = dp[5] + 1;
    • 4;
  • 이 중 최솟값을 대입한다.
  • dp[6] = 2;

• dp[7] = 4;

  • N = 7은 3으로도, 2로도 나누어 떨어지지 않기 때문에
  • -1연산만 실행한다.
  • dp[7] = dp[6] + 1 = 4;

• dp[8] = 3;

  • N = 8일때는 2로 나누어 떨어진다.
    • dp[8] = dp[8 / 2 = (4)] + 1;
    • dp[8] = 2 + 1;
  • -1연산도 해보면
    • dp[8] = dp[7] + 1;
  • dp[8] = 5;

• dp[9] = 2;

  • N = 9 일때는 3으로 나누어 떨어진다.
    • dp[9] = dp[9 / 3 = (3)] + 1;
    • dp[9] = 2;
  • 또한 -1연산을 하면
    • dp[9] = dp[8] + 1;
    • dp[9] = 4;

• dp[10] = 3;

  • 10은 2로 나누어 떨어진다.
    • dp[10] = dp[10 / 2 = (5)] + 1;
      • dp[10] = 3 + 1 = 4;
  • -1연산을 하면
    • dp[10] = dp[9] + 1;
    • dp[10] = 3;
  • dp[10]에서는 반대로 2로 나누어 떨어지지만 -1을 한 연산이 더 작은 값이 나온다.
  • 이처럼 예외값이 존재하기 때문에 조심하여야 한다.

• 따라서 위의 식대로 코드를 슈도코드를 짜보면 아래와같다.

  • N 을 2로 나누어 떨어진다면 dp[N] = dp[N / 2] + 1;
  • N 이 3으로 나누어 떨어진다면 dp[N] = dp[N / 3] + 1;
  • 그리고 마지막으로 -1연산 dp[N] = dp[N - 1] + 1;
  • 위의 식 조건 중에서 가장 작은 최솟값을 넣게 되는것이다.

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

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

dp[N] = Math.min(dp[N], do[N - 1] + 1);

여기서 else if 를 쓰지않은 이유는 2로도 나누어떨어질 수 있고, 3으로도 나누어 떨어질 수 있기 때문이다.
맨 처음 dp[N] = N 으로 초기화한 이유는 이 후 조건에서 최솟값을 dp[N]에 대입헤야 하기 때문이다.

전체코드

전체코드에는 top-down과 bottom-up 코드가 모두 있다.

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

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

        int N = Integer.parseInt(br.readLine());

        DP = new Integer[N + 1];
        DP[0] = DP[1] = 0;


//        System.out.println(recur(N));
        top_down(N);

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

    private static int recur(int N) {
        if (DP[N] == null) {
            if (N % 6 == 0) {
                DP[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
            } else if (N % 3 == 0) {
                DP[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
            } else if (N % 2 == 0) {
                DP[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
            } else {
                DP[N] = recur(N - 1) + 1;
            }
        }
        return DP[N];
    }

    private static void top_down(int N) {

        for(int i = 2; i <= N; i++) {
            DP[i] = i;
            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);
            }

            DP[i] = Math.min(DP[i], DP[i - 1] + 1);
        }
    }
}

정리

이번문제에서는 몇 가지 조건이 존재했다.
1. 2로 나누기
2. 3으로 나누기
3. -1 연산하기

이 문제의 핵심은 N이 주어졌을 때 N에 대하여 조건들 중 부합하는 조건들끼리 비교하여 최솟값을 dp 배열에 넣는것이었다.
정리하자면, bottom-up기준 1부터 N까지 순회하며 조건에 부합하는 값들 중 최솟값을 dp에 넣는것이 주요포인트였다.