입력예시에서 힌트를 얻어 문제를 풀었다. 😉
나는 삼각형을 이루는 정수를 tri[][]
에 저장했는데, tri[i][j]
에서 접근할 수 있는 수는 tri[i+1][j]
와 tri[i+1][j+1]
이었다. 그래서 그 둘 중에 큰 값과 자기 자신을 더해서 dp[i][j]
에 저장해두면 된다.
나는 밑에 줄부터 시작했다. 그래서 마지막 줄의 dp
는 (dp[N-1]
) 미리 값을 채워주었다. 👉🏻 dp[N-1] = tri[N-1]
import java.util.Scanner;
public class boj1932 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[][] tri = new int[N][N];
int[][] dp = new int[N][N];
for(int i = 0; i < N; i++) {
for(int j = 0; j < i+1; j++) {
tri[i][j] = sc.nextInt();
}
}
dp[N-1] = tri[N-1];
for(int i = N-2; i >= 0; i--) {
for(int j = 0; j <= i; j++) {
dp[i][j] = tri[i][j] + Math.max(dp[i+1][j], dp[i+1][j+1]);
}
}
System.out.println(dp[0][0]);
}
}
다른 사람들 풀이를 보면 위에서부터 하는 경우도 많았다. 그럴 땐 max
변수를 따로 두고 최댓값을 저장하면서 하면 된다.