정수 삼각형
위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때,
이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라.
아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다.
삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
입력
첫째 줄에 삼각형의 크기 n (1 ≤ n ≤ 500)이 주어지고,
둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
예제 입력 1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
예제 출력 1
30
출처
- Olympiad > International Olympiad in Informatics > IOI 1994 > Day 1 1번
- Olympiad > USA Computing Olympiad > 2005-2006 Season > USACO December 2005 Contest > Bronze ?번
- Olympiad > USA Computing Olympiad > 1999-2000 Season > USACO Fall 1999 Contest > Gold 1번
문제의 오타를 찾은 사람: apjw6112, Martian, paranocean
잘못된 데이터를 찾은 사람: thanatos0128
잘못된 조건을 찾은 사람: djm03178
데이터를 추가한 사람: eunhyekim1223, hwangtmdals
알고리즘 분류
- 다이나믹 프로그래밍
문제 풀이
오늘 간만에 다이내믹 프로그래밍, 즉 동적 계획법을 다룬다. 쉬운 동적 계획법 문제들은 대체로 그냥 무작정 앞에 것에 뒤에 것을 더하는 방식으로 진행되는 경우가 잦다. 그러나 중급 난이도에서는 반드시 생각해야 할 것이 있다.
- 상향식 vs 하향식
- 현재 줄 vs 다음 줄
- 현재 줄에 더함 vs 다음 줄에 더함
- 그리디 범위
- 둘 혹은 여럿 중 하나를 더할지 말지 조건이 복잡한 그리디
- 둘 혹은 여럿 중 최대/최소/평균처럼 명확한 조건으로 더하는 그리디
- 이 때는 바로 조건문 걸기 전에
max,min,sum(arr) / arr_len - 그래도 안 될 느낌일 때 조건문 분기
- 이 때는 바로 조건문 걸기 전에
이러한 방향으로 사고 체계를 잡아야 한다.
이 문제는 삼각형에서 규칙을 따라 올라갔을 때의 최대 합을 구하는 것이다. 이 경로를 구하는 방법은 조금 사고력이 필요하다.
접근법
맨 아랫줄 바로 이전부터 시작한다.
- 맨 아랫줄 바로 이전 특정 칸 ㄱ에서
- 맨 아랫줄의 움직일 수 있는 칸에 쓰인 값 중 최대를 찾는다.
- 최대를 현재 칸 ㄱ에 더해 준다.
이러한 가벼운 형태의 그리디로 동작한다. 이런 코드 유형은 그다지 암기할 것도 아니고 기억 및 숙달만 간단히 해 주면 익힐 수 있다.
다시 한 번 말하지만 접근법을 손보단 머리가 기억하고 있어야 한다.
다른 모든 방법들보다 좋은 것은 직접 작성해 보는 것이다. 실제 구현된 C언어 답안을 보면서 따라가자.
C언어 답안
#include <stdio.h>
#include <string.h>
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
typedef struct position {
int x;
int y;
} pos_t;
// When solving a coding test, clarifying each boundaries are important.
// Declare get_l_pos and get_r_pos to prevent spaghetti code.
// Move a position(leftwards, strictly down)
pos_t get_l_pos(pos_t p) {
pos_t l_pos = p;
// Only increases y, so it can drop down vertically
l_pos.y++;
return l_pos;
}
// Move a position(rightwards, horizontally move after stepping down a location.)
pos_t get_r_pos(pos_t p) {
pos_t r_pos = get_l_pos(p);
// Step A. get_l_pos to drop a row.
// Step B. increment x variable to move right.
r_pos.x++;
return r_pos;
}
int main() {
int n;
scanf("%d", &n);
// an array to hold 'an integer triangle'
long arr[n+1][n+1]; // 1 <= n <= 500, max size == (500 * 500) / 2 == 125000 (unit: 64-bit integer)
memset(arr, 0, sizeof(arr));
// In this scenario, this uses 1-based index.
// Max size is 251001 * 8 byte, 2008008 byte. Near 2-2.5 MB(approx.)
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= i; j++) {
scanf("%ld", &arr[i][j]);
}
}
// exclude last line, last line has no route
for(int i = n - 1; i >= 1; i--) {
for(int j = i; j >= 1; j--) {
pos_t p;
p.x = j; // col
p.y = i; // row
pos_t l_pos = get_l_pos(p); // get left move
pos_t r_pos = get_r_pos(p); // get right move
// implement 'Greedy' method
// if this cannot traverse full directions, just add current value to next position.
// Greedy was selected to prevent potential weight contamination
long l_pos_new_val = arr[l_pos.y][l_pos.x] + arr[p.y][p.x];
long r_pos_new_val = arr[r_pos.y][r_pos.x] + arr[p.y][p.x];
arr[p.y][p.x] = MAX(l_pos_new_val, r_pos_new_val);
}
}
// prints max value
printf("%ld", arr[1][1]);
return 0;
}
코드 역시 주석을 상세하게 달아 두었다. 이것으로 복습은 충분할 것이다.
P.S
이 게시물은 현재 활발하게 개발 중인 Nanox 에디터로 작성되었다. 아래 링크를 참고하기 바란다.