문제링크
https://www.acmicpc.net/problem/1932
문제
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번째 줄까지 정수 삼각형이 주어진다.
출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
조건
- 시간 제한 : 2s
- 메모리 제한 : 128MB
해설
각 숫자에 0부터 순서대로 번호를 매겨서 맨 위에서 아래로 내려오면서 값을 더해 최대 합을 구해나간다. 가장 아래에 도착하면, 구한 합들을 비교하여 그 중 가장 큰 값을 선택하여 출력한다. 여기에서 DP를 사용하면 쉽게 문제를 해결할 수 있다.
풀이
우선 삼각형의 숫자들에 번호를 붙여보자
0 : 0
1 : 1 2
2 : 3 4 5
3 : 6 7 8 9
4 : 10 11 12 13 14
5 : 15 16 17 18 19 20
. : ...편의상 왼쪽의 수를 층이라고 부르자. 각 층의 첫번째 숫자들은 자연수의 누적합과 같은 모양을 보인다. ( 1, 1+2, 1+2+3, 1+2+3+4, ... ) 각 층 안에서 숫자의 증가는 누적 합에 0부터 시작하여 층 수까지 더한 값과 같다. (3층 → 6+0, 6+1, 6+2, 6+3) 이를 이용해 각 숫자의 위치를 나타내는 식은 i*(i+1)/2 + j로 볼 수 있다. 여기에서 i는 층, j는 층 내에서 증가하는 숫자이다. 모든 위치를 정확히 명시하며 값을 입력받는 방법은 아래와 같다.
for(int i = 0; i < n; i++) {
for(int j = 0; j <= i; j++) {
cin >> arr[i*(i+1)/2 + j];
}
}
2층까지 최댓값으로 선택을 완료했다고 할 때, 3층의 7에 접근할 수 있는 위치는 3, 4이다. 3층까지 선택을 한 뒤 4층의 11은 6과 7에서 접근할 수 있다. 이를 수식적으로 말하자면, i*(i+1)/2 + j에 접근할 수 있는 위치는 (i-1)*i/2 + j-1 과 (i-1)*i/2 + j이다. 둘 중 큰 값을 가져와 해당 위치의 값을 더해주면 그 위치까지의 선택할 수 있는 최댓값이 된다. 0층에 대해서는 index가 음수인 값에 접근하게 되므로, arr[0]은 제외해주었다.
// 초기값 대입
cin >> arr[0];
for(int i = 1; i < n; i++) {
for(int j = 0; j <= i; j++) {
cin >> arr[i*(i+1)/2 + j];
arr[i*(i+1)/2 + j] += max(arr[(i-1)*i/2 + j], arr[(i-1)*i/2 + j-1]);
}
}
그러나, 위와 같은 방식으로 하면 각 층의 가장 왼쪽, 가장 오른쪽에 있는 위치에서는 잘못된 값을 가져오게 된다. (3층의 가장 왼쪽인 6번은 2층의 3번과 1층의 2번에 접근) 그러므로, 이를 정상적으로 처리하기 위해서 j가 0이거나 i인 경우에는 예외처리를 해주어야 한다.
// 초기값 대입
cin >> arr[0];
for(int i = 1; i < n; i++) {
for(int j = 0; j <= i; j++) {
cin >> arr[i*(i+1)/2 + j];
if(j==0) {
arr[i*(i+1)/2 + j] += arr[(i-1)*i/2 + j];
} else if (j==i){
arr[i*(i+1)/2 + j] += arr[(i-1)*i/2 + j-1];
} else {
arr[i*(i+1)/2 + j] += max(arr[(i-1)*i/2 + j], arr[(i-1)*i/2 + j-1]);
}
}
}
위 코드를 거치고 나면 가장 아랫층에는 각 선택지에 대한 최댓값들이 저장되어있다. n번째 층을 돌면서 최댓값을 찾아 출력해주면 원하는 결과를 얻을 수 있다.
int max = 0;
for(int j = 0; j < n; j++) {
if(arr[n*(n-1)/2 + j] > max) max = arr[n*(n-1)/2+j];
}
cout << max;
코멘트
이정도는 쉽지. 후후후. 코드도 읽기 쉽게 나름 깔끔하게 짠 것 같아.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main () {
int n;
cin >> n;
vector<int> arr(n*(n+1)/2);
// 초기값 대입
cin >> arr[0];
for(int i = 1; i < n; i++) {
for(int j = 0; j <= i; j++) {
cin >> arr[i*(i+1)/2 + j];
if(j==0) {
arr[i*(i+1)/2 + j] += arr[(i-1)*i/2 + j];
} else if (j==i){
arr[i*(i+1)/2 + j] += arr[(i-1)*i/2 + j-1];
} else {
arr[i*(i+1)/2 + j] += max(arr[(i-1)*i/2 + j], arr[(i-1)*i/2 + j-1]);
}
}
}
int max = 0;
for(int j = 0; j < n; j++) {
if(arr[n*(n-1)/2 + j] > max) max = arr[n*(n-1)/2+j];
}
cout << max;
return 0;
}
Uploaded by Notion2Tistory v1.1.0