https://www.acmicpc.net/problem/15645
시간 제한 | 메모리 제한 | solved.ac 티어 |
1초 | 512MB | 실버 1 |
N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.
먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.
별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.
입력
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.
출력
첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.
그간 학업으로 인해 PS문제를 잠시 내려놓고 지냈다가, 방학이후로 탱자탱자 놀았다. 뭔가 X되가는게 느껴져서 PS 재활훈련을 위해 랜덤 실버 문제 디펜스를 시작했다. 그래서 걸린게 실버1 DP문제... 억까하는게 분명하다.
잡설은 그만하고, DP문제임에도 이 문제는 상당히 웰노운? 같은 풀이법을 적용할 수 있다.
DP는 복잡한 문제를 작은문제에서 확장해나가는 것이다. 예제 케이스를 통해 살펴보자. 해당 케이스는 백준 예제 입력 케이스이다.
0열 | 1열 | 2열 | |
0행 | 1 | 2 | 3 |
1행 | 4 | 5 | 6 |
2행 | 4 | 9 | 0 |
0행에서 시작하여 내려오기 때문에 일단 0행만 살펴보도록 하자.
0열 | 1열 | 2열 | |
0행 | 1 | 2 | 3 |
0열 | 1열 | 2열 | |
0행까지의 최대 | 1 | 2 | 3 |
이제 1행까지 붙여서 생각해보자. 지금까지의 상황을 통해 조금 수정해보면
0열 | 1열 | 2열 | |
0행까지의 최대 | 1 | 2 | 3 |
1행 | 4 | 5 | 6 |
이 될 것이다. 이제 다시 각 열에 도착했을 때 만들 수 있는 최댓값은 다음과 같을 것이다.
0열 | 1열 | 2열 | |
1행까지의 최대 | 6 (1 + 4, 2 + 4) | 8 (1 + 5, 2 + 5, 3 + 5) | 9 (2 + 6, 3 + 6) |
우리가 알고자 하는건 결국 최댓값이기 때문에 어떻게 왔던간에 최댓값만 저장하면 된다. 이제 마지막 2행까지 따져보자. 역시 지금까지의 상황을 통해 수정하면 다음과 같아진다.
0열 | 1열 | 2열 | |
1행까지의 최대 | 6 | 8 | 9 |
2행 | 4 | 9 | 0 |
또 각 열에 도착했을 때 만들 수 있는 최댓값을 구해보자.
0열 | 1열 | 2열 | |
2행까지의 최대 | 12 (6 + 4, 8 + 4) | 18 (6 + 9, 8 + 9, 9 + 9) | 9 (8 + 0, 9 + 0) |
이제 각 열에 도달했을때 구할 수 있는 최댓값을 모두 구했다. 이중에서 제일 큰 값이 답이 될 것이고, 답은 18이다. 이를 코드로 구현하면 다음과 같다. 최솟값도 같은 방식으로 구하면 된다.
#include <bits/stdc++.h>
using namespace std;
#define MAXVALUE (int)1e7
int row;
int col = 3;
vector<vector<int>> board;
void input() {
cin >> row;
board.resize(row);
for (auto& line : board) {
line.resize(col);
for (int& x : line) cin >> x;
}
}
int getMaxDp() {
int dp[row][col];
int dx[3] = {-1, 0, 1};
int prev;
for (int i = 0; i < col; i++) dp[0][i] = board[0][i];
fill(&dp[1][0], &dp[row - 1][col], 0);
for (int i = 1; i < row; i++) { // 라인 선택
for(int j = 0; j < col; j++) { // 해당 라인에서 원소 선택
for (int k = 0; k < 3; k++) { // 인덱스 변화량 선택
prev = j + dx[k];
if (prev < 0 || prev >= col) continue;
dp[i][j] = max(dp[i][j], board[i][j] + dp[i - 1][prev]);
}
}
}
sort(dp[row - 1], dp[row - 1] + col);
return dp[row - 1][col - 1];
}
int getMinDp() {
int dp[row][col];
int dx[3] = {-1, 0, 1};
int prev;
for (int i = 0; i < col; i++) dp[0][i] = board[0][i];
fill(&dp[1][0], &dp[row - 1][col], MAXVALUE);
for (int i = 1; i < row; i++) { // 라인 선택
for(int j = 0; j < col; j++) { // 해당 라인에서 원소 선택
for (int k = 0; k < 3; k++) { // 인덱스 변화량 선택
prev = j + dx[k];
if (prev < 0 || prev >= col) continue;
dp[i][j] = min(dp[i][j], board[i][j] + dp[i - 1][prev]);
}
}
}
sort(dp[row - 1], dp[row - 1] + col);
return dp[row - 1][0];
}
void sol() {
int maxAnswer = getMaxDp();
int minAnswer = getMinDp();
cout << maxAnswer << ' ' << minAnswer;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
input();
sol();
}
그래도 꽤 풀어본 유형의 DP문제라 다행이었다.
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 21920번 C++ 풀이 (1) | 2023.02.05 |
---|---|
백준 3005번 C++ 풀이 (1) | 2023.02.05 |
백준 10825번 C++ 풀이 (0) | 2023.02.05 |
백준 16401번 C++ 풀이 (0) | 2022.11.17 |
백준 13565번 C++ 풀이 (2) | 2022.11.08 |