링크 : https://www.acmicpc.net/problem/1932
문제 설명 :
![](https://blog.kakaocdn.net/dn/cI5NWD/btrac8gWHLT/PIk584HIXqJQkE6msKxe7K/img.png)
위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
입력 :
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
출력 :
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
예제 입력 :
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
예제 출력 :
30
접근법 :
1) 어떻게 풀 것인가?
문제의 정수 삼각형을 코드로 작성하기위해 n*n의 정사각형 모양 행렬로 만들고,
조건에 따라 그림을 그려보면 아래와 같은 그림이 나온다.
각 화살표는 아래층으로 내려갈 수 있는 모든 경우의 수이고,
화살표를 받는 입장에서는 받는 값들 중 큰 값을 받으면 된다.
즉, 첫번째 줄부터 시작해서 가능한 모든 경우의 수의 최댓값을
메모해나가면 (Memoization - DP) 자연스레 마지막 N번째 줄에서 최댓값을 구할 수 있다.
코드로 구현할때는 크게 2단계로 구현하면 된다.
* int[ ] = dp[i][j] 는 i 행 j열의 가능한 최댓값
① 아랫칸 값들과 값을 비교하는 과정은 아래와 같이 표현 가능하다.
dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j]); // 바로 밑(↓)에 칸과 비교
dp[i+1][j+1] = Math.max(dp[i+1][j+1], dp[i][j]); // 우측 대각선 아래(↘) 칸과 비교
② 한 줄이 끝나면 모든 줄에 해당 칸에서 얻을 수 있는 점수를 더해주는 과정
for (int j=1; j<=i+1; j++){
dp[i+1][j] += map[i+1][j];
}
합치면 DP가 구현되는 곳의 코드는 아래와 같다.
// 2. 1 ~ (N-1) Row에서 뿌려주는 DP 실행
dp[1][1] = map[1][1];
for (int i=1; i<=N-1; i++){
for (int j=1; j<=i; j++){
// 가능한 최댓값으로 갱신
dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j]);
dp[i+1][j+1] = Math.max(dp[i+1][j+1], dp[i][j]);
}
for (int j=1; j<=i+1; j++){
dp[i+1][j] += map[i+1][j];
}
}
기본적인 DP(Dynamic Programming), 동적계획법 문제로 전체 구현은 아래 Java 코드 참조.
2) 시간복잡도
1~N까지의 합이므로 N*(N-1)/2. 크게 잡아도 O(N^2), N은 500으로 넉넉함.
(Java 기준 280ms)
3) 공간복잡도
n이 500으로 500^2을 해도 int 배열로 넉넉함.
4) 풀면서 놓쳤던점
문제를 대충 읽고 삼각형의 뿌려지는 범위를 2칸이 아닌 3칸으로 더 넓게 해석함.
5) 이 문제를 통해 얻어갈 것
DP의 기본적 활용.
Java 코드 :
import java.io.*;
import java.util.*;
// 백준 1932
public class Main {
static int N, ans;
static int [][] map, dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
map = new int[N+1][N+1];
dp = new int[N+1][N+1];
// 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());
}
}
// 2. 1 ~ (N-1) Row에서 뿌려주는 DP 실행
dp[1][1] = map[1][1];
for (int i=1; i<=N-1; i++){
for (int j=1; j<=i; j++){
// 가능한 최댓값으로 갱신
dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j]);
dp[i+1][j+1] = Math.max(dp[i+1][j+1], dp[i][j]);
}
for (int j=1; j<=i+1; j++){
dp[i+1][j] += map[i+1][j];
}
}
// 3. 마지막 줄에서 가장 큰 값 찾아서 출력
for (int j=1; j<= N; j++){
ans = Math.max(ans, dp[N][j]);
}
bw.write(String.valueOf(ans));
bw.flush();
bw.close();
br.close();
}
}
'알고리즘 Algorithm > BOJ 백준 (초급~중급)' 카테고리의 다른 글
[BOJ 백준] 교수님은 기다리지 않는다(3830) Java (0) | 2021.07.26 |
---|---|
[BOJ 백준] 단절점(11266) Java (0) | 2021.07.25 |
[BOJ 백준] 플로이드(11404) Java (0) | 2021.07.22 |
[BOJ 백준] 최단경로(1753) Java (0) | 2021.07.21 |
그래프 & DP(동적계획법) 백준 36문제 (0) | 2021.07.20 |