백준 자바 :: 정수 삼각형 (DP) / 1, 2, 3 더하기 (DP) / 계단오르기 (DP)

처음으로 풀어본 dp문제

젤 정답율 높은 거 골랐다.

대략 어떤 느낌인지 알겠다..!

 

 

 

 

정수 삼각형

import java.util.*;

import java.io.*;

public class Main{

    static int N;

    static int[][] arr;

    static int[][] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;

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

        arr = new int[N][N];

        dp = new int[N][N];

        // arr 저장하기

        for (int i = 0; i < N; i++){

            st = new StringTokenizer(br.readLine());

            for (int j = 0; j <= i; j++){ // 삼각형 입력시 값 주의!!!!!!!

                arr[i][j] = Integer.parseInt(st.nextToken());

            }

        }

        // dp 모두 -1로 초기화

        for (int[] row : dp){

            Arrays.fill(row, -1);

        }

        // dp 마지막 값만 넣기

        for (int i = 0; i < N; i++){

            dp[N-1][i] = arr[N-1][i];

        }

        System.out.println(recursive(0,0));

    }

    static int recursive(int x, int y){

        if(x == N-1){

            return dp[x][y];

        }

        if(dp[x][y] == -1){

            dp[x][y] = Math.max(recursive(x+1, y), recursive(x+1, y+1)) + arr[x][y];

        }

        return dp[x][y];

    }

}

 

 

 

 

1, 2, 3 더하기

 

 

 

 

import java.util.*;

import java.io.*;

public class Main{

    static int N;

    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[11];

       

        dp[1] = 1;

        dp[2] = 2;

        dp[3] = 4;

        for(int i = 4; i <=10; i++){

            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

        }

        for(int i = 0; i < N; i++){

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

            System.out.println(dp[answer]);

        }

    }

}

 

 

 

 

 

계단오르기

 

 

 

 

 

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[] stair = new int[301];

        int[] dp = new int[301];

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

        for (int i = 1; i <= N; i++){

            stair[i] = Integer.parseInt(br.readLine());

        }

        dp[1] = stair[1];

        dp[2] = stair[1] + stair[2];

        dp[3] = Math.max(stair[1], stair[2]) + stair[3];

        for (int i = 4; i <= N ; i++){

            dp[i] = Math.max(dp[i-3] + stair[i-1], dp[i-2]) + stair[i];

        }

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

    }

}