[백준 1921번] 정수 삼각형

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

피라미드 모양의 정수 삼각형이 있을 때, 맨 위층부터 맨 아래층 까지 대각선 왼쪽 또는 오른쪽으로만 이동하여 내려올 때 선택된 수의 합이 최대가 되는 값을 찾는 문제이다.

정수의 범위 : 0<= x <= 9999

피라미드의 높이 : 1<= n<= 500

 

2. 나의 방식대로 문제를 재정의 하자.

맨 윗줄부터 각 원소마다 최대가 되는 값을 memorization하며 구현한다.

 

 

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

일단, 주어진 입력값을 저장하는 map[][] 배열을 생성한다.

같은 크기의 dp[][]를 생성해 윗줄에서부터 각 원소의 위치까지 내려올 때의 최댓값을 저장한다.

 

중간과정으로 3가지의 경우가 있다.

1. 맨 왼쪽 줄인 경우

이 경우에는 오른쪽 위의 정수만 존재하므로 dp[i][j] = dp[i-1][j] + map[i][j] 연산을 한다.

2. 맨 오른쪽 줄인 경우

마찬가지로 왼쪽 위의 정수만 존재하므로 dp[i][j] = dp[i-1][j-1] + map[i][j] 연산을 한다.

3. 가운데 위치한 줄인 경우

왼쪽위, 오른쪽 위 모두 존재하므로 둘중 더 큰값을 선택하여

dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + map[i][j] 연산을 한다.

 

모든 연산이 끝난 후 맨 아랫줄 값 중에서 가장 큰 값을 리턴한다.

 

4. 주의할 점은 무엇인가?

입력값의 범위에 0이 포함되어있으므로 배열을 int형으로 할 경우 0의 값이 주어진 입력값인지, 연산의 결과인지 알 수 없게 된다. 그러므로 Integer[][]를 사용하는것이 맞다.

 

*****

하지만 보통의 경우에는 Integer[] 배열은 int[] 배열의 4배정도의 메모리가 소모된다고 하니 자칫 재귀가 매우 깊어지거나 입력 값이 많은 경우에는 객체배열을 피하는게 좋다.

*****

 

6. 풀이 과정

1) 반복문

import java.io.*;
import java.util.*;

public class q1932 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        Integer n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[][] map = new int[n][n];
        int[][] dp = new int[n][n];
        int result = 0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j <= i; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp[0][0] = map[0][0];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) { //맨 왼쪽줄
                    dp[i][j] = dp[i - 1][j] + map[i][j];
                } else if (j == i) { //맨 오른쪽 줄
                    dp[i][j] = dp[i - 1][j - 1] + map[i][j];
                } else { //가운데 줄
                    dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + map[i][j];
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            result = Math.max(result, dp[n - 1][i]);
        }
        

        bw.write(result+"\n");

        br.close();
        bw.flush();
        bw.close();
    }
}

 

2) 재귀문

import java.io.*;
import java.util.*;

public class q1932 {

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

        Integer n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[][] map = new int[n][n];
        int[][] dp = new int[n][n];
        int result = 0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j <= i; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            result = Math.max(result, calculation(n - 1, i, dp, map));
        }

        bw.write(result + "\n");

        br.close();
        bw.flush();
        bw.close();
    }
    
    
    static Integer calculation(int i, int j, int[][] dp, int[][] map) {
        if (i == 0 && j == 0) {
            return map[i][j];
        }

        if (dp[i][j] != 0) {
            return dp[i][j];
        }

        if (j == 0) { // 맨 왼쪽줄
            dp[i][j] = calculation(i-1,j,dp,map) + map[i][j];
        } else if (j == i) { // 맨 오른쪽 줄
            dp[i][j] = calculation(i - 1, j-1, dp, map) + map[i][j];
        } else { // 가운데 줄
            dp[i][j] = Math.max(calculation(i - 1, j - 1, dp, map), calculation(i - 1, j, dp, map)) + map[i][j];
        }


        return dp[i][j];
    }
}

 

7. 개선점

다른 풀이 중 맨 꼭대기가 아닌 맨 아랫줄 부터 연산을 시작하는 방법이 있었다.

아래에서 부터 최댓값을 찾아 탐색할 경우 따로 Math.max()연산을 해줄 필요 없이 dp[0][0] 값이 최대값이 되어 연산이 간단해진다.

import java.io.*;
import java.util.*;

public class q1932 {

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

        Integer n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[][] map = new int[n][n];
        int[][] dp = new int[n][n];
        int result = 0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j <= i; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        for (int i = 0; i < n; i++) {
            dp[n - 1][i] = map[n - 1][i];
        }

        for (int i = n-2; i >=0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.max(dp[i +1][j], dp[i+1][j+1]) + map[i][j];
            }
        }

        result = dp[0][0];

        bw.write(result + "\n");

        br.close();
        bw.flush();
        bw.close();
    }
}