[Silver I] 정수 삼각형 - 1932
성능 요약
메모리: 29124 KB, 시간: 248 ms
분류
다이나믹 프로그래밍
제출 일자
2025년 1월 3일 10:03:48
문제 설명
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
구하고자 하는 것
정수 삼각형에서 합이 최대가 되는 경로가 있는 수의 합을 구해야 한다.
풀이 설계하기
처음에는 문제에 나온 모양대로 삼각형을 만들어야 하나? 라고 생각했다.
그러나 문제에 나온 규칙 따라서 시뮬레이션을 하다 보니 그럴 필요는 없었다
7
38
810
2744
45265
와 같은 모양으로 하더라도 문제는 없었다.
그리고 수의 범위는 (0 이상-9999 이하)이므로 10000 * 500을 하더라도 int 범위를 초과하지 않는다.
풀이를 설계하기 위해 시뮬레이션을 해 보면,
- 첫째 줄은 7밖에 선택지가 없다.
- 둘째 줄은 3 + 7, 8 + 7의 가지가 생긴다
- 셋째 줄은 (3 + 7 + 8), max((3 + 7 + 1), (8 + 7 + 1)), (8 + 7 + 0)이 된다.
점화식 설계하기
사실 이 문제는 점화식 세우기는 아주 어렵지 않았다.
문제 조건 따라 윗 줄을 기준으로 하면 하단 좌-우 대각선, 아랫 줄을 기준으로 하면 상단 좌-우 대각선에 있는 수를 택할 수 있다.
그리고 그 자리에까지 오는 최대 경로를 저장한다면 점화식을 세울 수 있다.
수를 저장할 때, numbers[i][j]가 i번째 줄의 j번째 수라면 dp[i][j]는 i번째 줄의 j 번째 위치에서의 최대 경로를 저장한다.
그리고 위의 규칙을 바탕으로 점화식을 세우면
- 하단 기준 - dp[i + 1][j + k] = Math.max(dp[i + 1][j + k], dp[i][j] + numbers[i + 1][j + k]);
- 상단 기준 - dp[i][j] = Math.max(dp[i][j], dp[i - 1][cc] + numberTriangle[i][j]);
여기서 k는 0 혹은 1, cc는 상단의 j-1, j를 나타내는 좌표이다.
하단 코드를 보면 알 수 있을 것인데, 둘 다 좌우 대각선을 나타낸다.
현재 위치의 최대값 = (현재 기준)바로 위 칸의 수와 그 수의 좌측에 있는 수 중 최대값 (유효한 위치인지 신경쓸 것)
시간 복잡도
i번째 줄에서는(i가 0부터) i+1개의 수를 체크하고, i+1개의 수마다 최대 2번의 대입이 발생한다.
계산을 한다면 (1 + 2 + 3 + ... + N-1 + N) x 2
-> (N (N-1)) / 2 x 2
-> (N (N-1))
따라서 O(N ^ 2) 정도의 시간 복잡도가 발생한다.
N의 최대가 500이므로 500의 제곱은 25000 정도면 시간 내 통과 가능하다.
풀이
- 위에서 아래로 전파
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] numbers = new int[N][N];
int[][] dp = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < i + 1; j++) {
numbers[i][j] = Integer.parseInt(st.nextToken());
}
}
dp[0][0] = numbers[0][0];
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < i + 1; j++) {
for (int k = 0; k < 2; k++) {
dp[i + 1][j + k] = Math.max(dp[i + 1][j + k], dp[i][j] + numbers[i + 1][j + k]);
}
}
}
int answer = -1;
for (int i = 0; i < N; i++) {
answer = Math.max(answer, dp[N - 1][i]);
}
System.out.println(answer);
}
}
2.아래에서 위의 수를 활용
import java.io.*;
import java.util.*;
public class Main {
static int[] dc = {-1, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[][] numberTriangle = new int[N][N];
int[][] dp = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < i + 1; j++) {
numberTriangle[i][j] = Integer.parseInt(st.nextToken());
}
}
dp[0][0] = numberTriangle[0][0];
for (int i = 1; i < N; i++) {
for (int j = 0; j < i + 1; j++) {
for (int k = 0; k < 2; k++) {
int cc = j + dc[k];
if(cc < 0 || N <= cc) continue;
dp[i][j] = Math.max(dp[i][j], dp[i - 1][cc] + numberTriangle[i][j]);
}
}
}
int answer = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
answer = Math.max(dp[N-1][i], answer);
}
System.out.println(answer);
}
}사실 2번을 먼저 풀고 1번 식으로 혹시나 해서 풀어 보았는데, 이래저래 1번 코드가 좀 더 깔끔한 것 같다.
