1932_정수 삼각형 (JAVA)

1932번: 정수 삼각형

 

 

** DFS를 이용해 재귀로 풀면 - 시간 초과가 난다! (틀린 코드)

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

public class Main {
    static int n;
    static int[][] map;
    static int ans = 0;

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

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];

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

        dfs(0,0, 0, 1);
        System.out.println(ans);
    }

    private static void dfs(int cur_x, int cur_y, int sum, int cnt){
        sum += map[cur_x][cur_y];

        if(cnt==n){
            ans = Math.max(ans, sum);
            return;
        }

        cur_x += 1;
        if(cur_x>=0&&cur_x<n){
            if(cur_y>=0&&cur_y<n){
                if(map[cur_x][cur_y] != -1)
                    dfs(cur_x, cur_y, sum, cnt+1);
            }
            if(cur_y+1>=0&&cur_y+1<n){
                if(map[cur_x][cur_y+1] != -1)
                    dfs(cur_x, cur_y+1, sum, cnt+1);
            }
        }
    }
}

 

map[0][0] 부터 n개를 더했을 때 나올 수 있는 합의 모든 경우를 계산하면! 시간 초과가 난다.

 

sum값의 조건을 추가하면 경우의 수를 줄일 수 있지 않을까? 라고 생각해서

여러 조건을 추가했는데, 깔끔하게 정리되는 조건을 찾지 못했다.

 

계산 개수를 줄일 수 있는 방법이 무엇일까 생각하며 다시 풀었다.

 

 

 

 

 

☞ 맞은 코드!

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

public class Main {
    static int n;
    static int[][] map;

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

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                if(st.hasMoreTokens())
                    map[i][j] = Integer.parseInt(st.nextToken());
                else
                    map[i][j] = -1; //비어있는 부분 -1로 표시
            }
        }

        for(int i=n-1; i>0; i--){
            cal(i);
        }

        System.out.println(map[0][0]);
    }

    private static void cal(int row){
        int col = 0; //(행,열)일때 열의 인덱스
        
        for(int i=0; i<row+1; i++){
            if(i+1<row+1)
                map[row-1][col] += Math.max(map[row][i],map[row][i+1]);
            col++;
        }
    }
}

 

 

위 -> 아래로 내려가며 합을 더하는 방법으로 계속 생각했는데,

문제의 '맨 위층 부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때' 라는 말에 생각이 묶여 있었던 것 같다.

 

 

map[0][0]인 맨 위 -> 아래로 합을 계산하며 내려가는 것이 아닌,

맨 아래 -> map[0][0] 까지 합을 계산하며 올라가는 것으로 생각을 아예 다르게 했다.

 

 

 

왼쪽 그림과 같은 입력이 주어졌을 때, 해결 방법은 다음과 같다.

 

각 자리에서 더할 수 있는 값은 두 개의 값이다.

즉, 맨 위의 값인 7에서 더할 수 있는 값은 3과 8, 그 다음 행의 3에서 더할 수 있는 값은 8과 1이다.

 

 

이를 거꾸로 봐보자.

가장 아래 행 : 4 5 2 6 5 에서,

4와 5는 그 위의 행의 첫 번째 숫자인 2에 더해질 수 있다.

5와 2는 그 위의 행의 두 번째 숫자인 7에 더해질 수 있고, 2와 6은 4에, 6과 5는 4에 더해질 수 있다.

 

본 문제는 '합의 최대값'을 구해야 하므로, 더해질 수 있는 값 중에서 최대값을 더하여 합을 계산한다.

오른쪽 그림을 참고하여 같이 보면,

4와 5 중 더 큰 값인 5를 그 위의 행의 첫 번째 숫자에 더하여 저장한다. (2+Math.max(4,5)=7)

 

 

 

가장 아래 행의 원소를 2개씩 묶어 최대값을 그 위의 행에 더하는 과정은 위의 그림과 같다.

 

 

이 방법은 모든 합을 탐색하면서, 계산 개수를 줄일 수 있다. <- 시간 초과가 나지 않음!!