https://www.acmicpc.net/problem/2096
N줄에 0 이상 9 이하의 정수가 세 개씩 적혀 있다. 내려가기 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이다. 먼저, 처음에 적혀 있는 세 개의 정수 중에서 하나를 골라 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때는 다음과 같은 규칙이 있다. 바로 아래 있는 수로 넘어가거나, 아래 있는 수와 붙어 있는 수로만 이동할 수 있다는 것이다.
숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수와 최소 점수를 구하는 문제다.
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
ex. 가능한 시간 복잡도, 알고리즘 선택
입출력 제한
- 1 ≤ N ≤ 100,000
- 0 ≤ 점수 ≤ 9
현재까지 얻은 점수들 중 최댓값과 최솟값을 저장할 dp 배열을 선언하고, 숫자표 점수 정보를 입력받으면서 채워나가야 한다. 현재 위치를 별표로 보고, 그 이전 줄에서 골랐을 수 있는 위치는 O로, 아닌 위치는 X로 보면 아래 그림처럼 나타낼 수 있다.
현재 dp 배열이 이전의 dp 배열의 상태에만 영향을 받기 때문에 N만큼의 배열을 선언하기 보단 2만큼 선언하고 bool 값을 통해 Toggle 키처럼 사용하면 메모리를 아낄 수 있다.
코드 설계하기
위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!
- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지
- N 입력받기
- 숫자판 정보(세 개의 정수 값)를 입력받으면서 dp 배열 채우기
- dp[i][j][k] → j번째 줄에 i번째 숫자를 골랐을 때 얻을 수 있는 누적 점수의 최댓값(k=0)과 최솟값(k=1)을 저장하는 배열
- 마지막 dp 배열 중 최댓값과 최솟값 출력하기
시도 회차 수정 사항 (Optional)
- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!
pass
정답 코드
#include <iostream>
#include <algorithm>
using namespace std;
int n,dp[3][2][2],a,b,c;
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
bool tog;
cin >> n;
for (int i=1; i<=n; i++) {
cin >> a >> b >> c;
tog = (i%2==1 ? true : false);
dp[0][tog][0] = a + max(dp[0][!tog][0],dp[1][!tog][0]);
dp[1][tog][0] = b + max({dp[0][!tog][0],dp[1][!tog][0],dp[2][!tog][0]});
dp[2][tog][0] = c + max(dp[1][!tog][0],dp[2][!tog][0]);
dp[0][tog][1] = a + min(dp[0][!tog][1],dp[1][!tog][1]);
dp[1][tog][1] = b + min({dp[0][!tog][1],dp[1][!tog][1],dp[2][!tog][1]});
dp[2][tog][1] = c + min(dp[1][!tog][1],dp[2][!tog][1]);
}
cout << max({dp[0][tog][0],dp[1][tog][0],dp[2][tog][0]}) << ' ' << min({dp[0][tog][1],dp[1][tog][1],dp[2][tog][1]});
}