백준 1932번 (java)

백준 1932번 정수 삼각형

---

관찰

1. 완전 탐색 - dfs를 활용해서 완전 탐색으로 마지막 줄에 갔을때마다 최대값을 갱신해줘서 답을 찾기! 500크기니깐 한번 풀어보자!

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

public class Main {
    static int n;
    static int[][] map;
    static int max;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        map = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= i; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // 탐색 시작
        max = 0;
        dfs(1,1, 0);

        System.out.println(max);

    }

    private static void dfs(int r, int c, int total) {
        if(r == n+1){
            if(total > max){
                max = total;
            }
            return;
        }
        dfs(r+1,c,total + map[r][c]);
        dfs(r+1,c+1,total + map[r][c]);
    }
}

2의 500승 시간이 걸린다.. 당연히 시간 초과 ㅜㅜ

2. dp 방식을 이용하자! - 가장 큰 값만 더해서 테이블을 채워간다면 마지막 줄에는 가장 큰 후보들만 남아있을 것!

정답코드

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

public class Main {
    static int n; // 삼각형의 높이
    static int[][] map; // 삼각형
    static int[][] dp; // dp 테이블
    static int max; // 최대값 : 정답
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        map = new int[n+1][n+1];
        dp = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= i; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // dp 시작!
        // 내 위에 있는 두가지 중 높은 것을 선택해서 내 것과 더해주는 식으로 만들어감!
        dp[1][1] = map[1][1];
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if(!isOut(i-1,j-1)){
                    dp[i][j] = dp[i-1][j-1] + map[i][j];
                }
                if(!isOut(i-1,j)){
                    int tmp = dp[i-1][j] + map[i][j];
                    if(tmp > dp[i][j]) dp[i][j] = tmp;
                }
            }
        }
        // 마지막 줄에 있는 값 중 최대를 출력하기!
        max = 0;
        for(int i=1;i<=n;i++){
            if(max < dp[n][i]) max = dp[n][i];
        }
        System.out.println(max);

    }
    private static boolean isOut(int i, int j) {
        return i<1 || j<1 || i>n || j>n;
    }
    // 기존 완탐 방식
    private static void dfs(int r, int c, int total) {
        if(r == n+1){
            if(total > max){
                max = total;
            }
            return;
        }
        dfs(r+1,c,total + map[r][c]);
        dfs(r+1,c+1,total + map[r][c]);
    }
}

풀이

dfs로 완전 탐색을 했을 때 불필요한 연산이 많아진다.. 하지만 dp로 올 수 있는 두 가지 경우의 수에서 큰 값을 골라서 더해주는 방식으로 채워줬을 때 마지막 줄에서 각각의 인덱스로 도착했을 경우의 가장 큰 값들을 저장하고 있게 된다! 2^500 -> 삼각형의 크기 로 시간 단축이 가능하다!

느낀점

처음에 완탐 기준으로 생각했을 때는 큰 값으로 들어가면 가능하지 않을까? 라는 생각을 했는데 반례가 엄청 많았고, dp를 이용해서 안전하게 모든 경우에 대해 큰 경향으로 만들어 준 후 마지막 줄에서 가장 큰 값을 찾아 해별할 수 있었다. 되게 좋은 문제인 것 같다!