[Silver I][JAVA]1932번 : 정수 삼각형

1932 정수 삼각형

난이도 : 실버 1
유형 : DP
https://www.acmicpc.net/problem/1932

알고리즘 [접근 방법]

위에서 아래로 내려오면서 최댓값 경로만 찾아서 하는 경우가 있는데 그렇게 하면 오답이 난다.

위 그림처럼 각 밑의 값 중 최댓값과 현 위치의 값을 더해나가면서 가는 방식이다. 그리고 DP[0][0]에 최종적으로 쌓인 누적 합이 최댓값이 될 것이다.

dp코드
입력받기 -> dp [0][0] 초기화 하기 -> 반복하여 재귀 실행하기 -> 최댓값 출력하기

// depth는 깊이(행), idx는 인덱스(열)를 의미
 
int find(int depth, int idx) {
 
	// 만약 맨 밑(깊이)의 행에 도달하면 해당 인덱스를 반환한다.
	if(depth == N - 1) return dp[depth][idx];
    
	// 만약 아직 탐색하지 않은 위치라면 다음 행의 양쪽 열 중 최댓값을 구함
	if (dp[depth][idx] == null) {
		/*
		 바로 다음행의 인덱스와 그 오른쪽의 인덱스 중 
		 큰 값 찾아 dp에 현재 인덱스의 값과 더하여 저장
		*/
		dp[depth][idx] = max(find(depth + 1, idx), find(depth + 1, idx + 1)) + arr[depth][idx];
	}
	return dp[depth][idx];
 
}

전체코드

package baekjoon_java.SilverI;

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

public class 정수삼각형 {
    static int[][] arr;
    static Integer[][] dp;
    static int N;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        arr = new int[N][N];
        dp = new Integer[N][N];
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");

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

        // 가장 마지막 행의 값들을 DP의 마지막 행에도 똑같이 복사
        for (int i = 0; i < N; i++) {
            dp[N - 1][i] = arr[N - 1][i];
        }
        System.out.println(find(0, 0));
    }

    static int find(int depth, int idx) {
        //마지막 행일 경우 현재 위치의 dp값 반환
        if (depth == N - 1)
            return dp[depth][idx];
        //탐색하지 않았던 값일 경우 다음행의 양쪽 값 비교
        if (dp[depth][idx] == null) {
            dp[depth][idx] = Math.max(find(depth + 1, idx), find(depth + 1, idx + 1)) + arr[depth][idx];
        }
        return dp[depth][idx];
    }
}