동적 계획법1(RGB 거리, 정수 삼각형)

[RGB 거리 _ 1149]

 

 

* 로직

• N개의 집마다 R,G,B를 칠할 때 드는 비용을 갖기 때문에 cost[N+1][3], dp[N+1][3]으로 설정한다
• 여기서 dp[N+1][3]은 해당 집까지 얻을 수 있는 비용의 최솟값을 저장한다
• 3가지 경우로 dp과정을 진행한다
  • dp[i][0]: i번째 집에서 R을 선택할 때 얻을 수 있는 최솟값
  • dp[i][1]: i번째 집에서 G을 선택할 때 얻을 수 있는 최솟값
  • dp[i][2]: i번째 집에서 B을 선택할 때 얻을 수 있는 최솟값
• 진행이 끝나면, dp[N][0], dp[N][1], dp[N][2] 중 최솟값을 출력한다

 

//RGB 거리
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Problem_1149 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int RGB_SIZE = 3;
        int[][] costs = new int[N+1][RGB_SIZE];    //R,G,B
        int[][] dp = new int[N+1][RGB_SIZE];

        for(int i=1; i<=N; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");

            for(int j=0; j<RGB_SIZE; ++j){
                costs[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp[1][0] = costs[1][0]; //R로 시작하는 경우
        dp[1][1] = costs[1][1]; //G로 시작하는 경우
        dp[1][2] = costs[1][2]; //B로 시작하는 경우
        for(int i=2; i<=N; ++i){
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + costs[i][0];  //dp[i][0]: i번째 집에서 R을 선택할 때 얻을 수 있는 최솟값
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + costs[i][1];  //dp[i][1]: i번째 집에서 G을 선택할 때 얻을 수 있는 최솟값
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + costs[i][2];  //dp[i][2]: i번째 집에서 B을 선택할 때 얻을 수 있는 최솟값
        }

        int answer = Math.min(dp[N][0], Math.min(dp[N][1], dp[N][2]));
        System.out.println(answer);
    }
}

 

 

[정수 삼각형 _ 1932]

 

 

* 로직

• 루트를 기준으로 양쪽 대각선에 대한 누적 합을 저장한다
• 저장이 안된 값들에 대해서 최댓값을 갱신한다
  • 이전 level에서 왼쪽과 오른쪽 대각선 중 최댓값과 현재 위치에 있는 값을 더해 값을 갱신한다
    dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangles[i][j]
• 마지막 level에 각각 누적합들이 존재하고, 이 중 최댓값을 출력한다

 

//정수 삼각형
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Problem_1932 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[][] triangles = new int[N][N];
        int[][] dp = new int[N][N];

        for(int i=0; i<N; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            int size = st.countTokens();

            for(int j=0; j<size; ++j){
                triangles[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //양쪽 대각선부터 누적 값을 저장
        dp[0][0] = triangles[0][0];
        for(int i=1; i<N; ++i){
            dp[i][0] = dp[i-1][0] + triangles[i][0];
            dp[i][i] = dp[i-1][i-1] + triangles[i][i];
        }

        //가운데 비어있는 값들을 갱신
        for(int i=2; i<N; ++i){
            for(int j=1; j<i; ++j){
                dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangles[i][j];
            }
        }

        int answer = 0;
        for(int j=0; j<N; ++j){
            answer = Math.max(answer, dp[N-1][j]);
        }
        System.out.println(answer);
    }
}