[4/23] DP 복습

DP 내용 복습을 하고 여태까지 풀었던 dp문제들을 다시 한번씩 풀어보았다.

백준 알고리즘

1463번 Java 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Scanner;   public class Main {     public static int[] d;       public static void main(String[] args) throws NumberFormatException, IOException {         // TODO Auto-generated method stub         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[1]=0;           for(int i=2;i<=n;i++) {             d[i]=d[i-1]+1;             if(i%2==0&&d[i]>d[i/2]+1) {                 d[i]=d[i/2]+1;             }             if(i%3==0&&d[i]>d[i/3]+1) {                 d[i]=d[i/3]+1;             }         }           bw.write(Integer.toString(d[n]));         bw.flush();         bw.close();       }          }   Colored by Color Scripter

cs

11726번 Java 코드

11727번 Java 코드

9095번 Java 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;   public class Main {     static int num = 0;       static int[] dp;       public static void main(String[] args) throws NumberFormatException, IOException {         // TODO Auto-generated method stub         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         num = Integer.parseInt(br.readLine());         dp = new int[12];         for (int i = 0; i < num; i++) {             System.out.println(process(Integer.parseInt(br.readLine())));         }       }       public static int process(int n) {         dp[0] = 1;         dp[1] = 1;         dp[2] = 2;         for (int i = 3; i <= n; i++) {             dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];         }         return dp[n];     }   }   Colored by Color Scripter

10844번 Java 코드

11057번 Java 코드

특히나 10844(쉬운 계단수), 11057(오르막수)문제는 이번에 복습하면서도 느낀 것이지만 dp 문제를 풀때는 배열의 크기 지정과 자료형 선정이 가장 중요한 것 같다. 수)는 이번에 다시 풀어보아도 선뜻 생각나지 않았기 때문에 다음에 한번 더 풀어봐야할 것 같다.

그리고 아주 어이없으면서도 멍청한 생각이 해결되었다. dp와 재귀함수의 차이점은 무엇인가? 라는 생각이다. 처음에 dp를 배울 때 dp와 재귀함수가 굉장히 비슷하다는 생각을 많이 했다.

이 둘의 차이점은 무엇일까? dp는 저장되어있는 값을 불러온다면 재귀함수는 값을 알아내기 위하여 함수를 한번 더 호출 한다는 점에서 차이점이 있다. 구조상으로는

f(n)=f(n-1)+f(n-2) -> 재귀함수

dp[n]=dp[n-1]+dp[n-2] -> DP

아주 유사해보이지만 사실상 재귀함수는 함수를 호출 하는 것이고, dp는 값을 불러온다는 점에서 차이점이 있다.