[백준] 1932번 정수 삼각형 자바 DP

목차

 

 

 

문제

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

 

 

 

 

풀이

일단 각 행에서 최대값을 선택해서 풀면 정답이 나오는지 확인해보자

7 -> 8 -> 1 -> 7 -> 5 = 28

정답인 30보다 작다. 이렇게 풀면 틀리게된다.

 

 

DP문제는 점화식을 세워서 풀어야하는 경우가 많다.

또한 이렇게 모든 경우의 수를 파악해서 "최소값", "최대값"을 찾게되면 값을 누적하여 처리해야한다.

아래 사진처럼 일단 경우의 수를 파악하고, 점화식을 이끌어낸다.

주황색 부분은 2가지 값을 가질 수 있는데, 비교하여 최대값을 저장한다.

 

점화식 (x, y)

A. [x][y] = [x-1][y-1] + [x][y]
B. [x][y] = [x-1][y] + [x][y]

 

1. x-1 < 0 인 경우는 연산이 불가하다. (배열 인덱스가 -1이 되니까)

2. 각 행의 맨 첫번째 값은 [x-1][y]만 수행하면된다.

3. 각 행의 맨 마지막 값은 [x-1][y-1]만 수행하면된다. 

 

 

 

 

 

제출코드

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


public class Main {

    static int[][] triangle = null;
    static int sum = 0;
    static int N = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        triangle = new int[N][N];

        //입력받기
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int count = st.countTokens();
            for (int j = 0; j < count; j++) {
                 triangle[i][j] = Integer.parseInt(st.nextToken());
                 process(i, j);
                 sum = Math.max(sum, triangle[i][j]);
            }
            //print();
        }

        System.out.println(sum);
    }



    private static void process(int i, int j) {
        //System.out.println("("+i+", "+j+")");

        if(i-1 < 0){
            return;
        }

        int tempA = 0;
        if(j-1 >= 0){
            tempA = triangle[i-1][j-1] + triangle[i][j];
        }
        int tempB = triangle[i-1][j] + triangle[i][j];

        triangle[i][j] = Math.max(tempA, tempB);
        //sum = Math.max(sum, triangle[i][j]);
        //N이 1일때 sum은 계속 0으로 나올수밖에 없다. 따라서 위쪽으로 코드를 옮겨주어야한다.
        
        //(3, 0)인 경우 tempB(2, 0)만 값이 할당된다.
        //(3, 3)인 경우 tempA(2, 2)와 tempB(2, 3)이 할당되지만 tempB(2, 3)은 어차피 0 이기 때문에 max값인 tempA값이 할당된다.
    }


    private static void print() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(triangle[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}