백준 1463 자바 dp 풀이 and bfs 풀이

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

1463번: 1로 만들기

 

Top-down은 가장 큰 문제를 방문 후 작은 문제를 호출하여 답을 찾는 방식이고,

Bottom-up은 가장 작은 문제들 부터 답을 구해가며 전체 문제의 답을 찾는 방식이다.

흔히 top-down은 재귀 호출을, bottom-up은 반복문을 이용해 구현한다.

Top-down 방식은 점화식을 이해하기 쉽다는 장점이 있고, Bottom-up 방식은 함수를 재귀 호출하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있다는 장점이 있다.

 

우선 D[j]를 구한다고 해보자 (1<j<=N) 

 

예외처리 (0과 1) (D[0] = 0, D[1] = 0;)

반복문은 2부터 N까지 진행. (여기부터 dp)

D[N]를 구할때 가능한 연산이 3가지 인데.

 

1을 빼는 것

j 를 만드는 방법은

j / 2 에서 2를 곱하는 방법과

j / 3 에서 3을 곱하는 방법과

j - 1 에서 1을 더하는 방법이 있다

 

따라서 저 세가지 방법중 적은 횟수로 만들 수 있는 녀석을 골라서 그 녀석에서 한 번의 추가적인 연산을 통해

j 를 만드는것이 최적이다

 

Bottom-up 방식  풀이 코드는 아래와 같다

 

import java.io.*;

public class t1463 {
  static int[] d;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    d = new int[N + 1];

    d[0] = 0;
    d[1] = 0;

    dp(N);

    bw.write(d[N] + "");

    br.close();
    bw.flush();
    bw.close();
  }
  private static int dp(int n) {
    for (int i = 2; i <= n; i++) {
      d[i] = d[i - 1] + 1;
      if (i % 2 == 0) {
        d[i] = Math.min(d[i], d[i / 2] + 1);
      }
      if (i % 3 == 0) {
        d[i] = Math.min(d[i], d[i / 3] + 1);
      }
    }
    return n;
  }
}

bfs 추가 중.