[BOJ] 2096 내려가기

https://www.acmicpc.net/problem/2096

2096번: 내려가기

문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

3
1 2 3
4 5 6
4 9 0

출력

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

18 6

---

최근에 어쩌다보니 그래프 위주로 풀었길래 DP를 한문제 풀었다.

상당히 쉽게 풀어서 DP 실력이 조금이나마 늘었나 했지만 문제가 쉬웠던 것 같다.

문제 푸는 방법보다 처음에 자료구조 짤 때 더 버벅거렸다.

그런데 풀고보니 메모리 제한이 4MB밖에 되지 않길래 자료구조를 다시 짜야했다.

 

PREV 행의 최대, 최소를 저장하고 그걸 사용해서 CUR 행에서 최대, 최소를 구했다.

CUR 행의 최대, 최소를 구하면 PREV 행으로 복사했다.

마지막에 최대, 최소만 구해주면 끝난다.

 

#include <iostream>
#include <utility>
#include <algorithm>

#define PREV 0
#define CUR 1

std::pair<int, int> score[2][3];
int data[3];
int N;

int main() {
	std::cin >> N;

	std::cin >> data[0] >> data[1] >> data[2];
	for (int i = 0; i < 3; i++)
		score[0][i].first = score[0][i].second = data[i];

	for (int i = 1; i < N; i++) {
		std::cin >> data[0] >> data[1] >> data[2];

		score[CUR][0].first = std::max(score[PREV][0].first, score[PREV][1].first) + data[0];
		score[CUR][0].second = std::min(score[PREV][0].second, score[PREV][1].second) + data[0];

		score[CUR][2].first = std::max(score[PREV][1].first, score[PREV][2].first) + data[2];
		score[CUR][2].second = std::min(score[PREV][1].second, score[PREV][2].second) + data[2];

		score[CUR][1].first = std::max(score[CUR][0].first - data[0], score[CUR][2].first - data[2]) + data[1];
		score[CUR][1].second = std::min(score[CUR][0].second - data[0], score[CUR][2].second - data[2]) + data[1];
		
		for (int i = 0; i < 3; i++) {
			score[PREV][i].first = score[CUR][i].first;
			score[PREV][i].second = score[CUR][i].second;
		}
	}

	int Max = score[PREV][0].first;
	int Min = score[PREV][0].second;
	
	for (int i = 1; i < 3; i++) {
		Max = std::max(Max, score[PREV][i].first);
		Min = std::min(Min, score[PREV][i].second);
	}

	std::cout << Max << " " << Min;

	return 0;
}

 

후기) 

알고리즘 분류에 슬라이딩 윈도우라고 되어있길래 뭐지 싶었다.

슬라이딩 윈도우라고 들어는 봤는데 뭔지 모르는 상태로 그냥 풀었다.

풀고보니 별게 아니라 중복되는 계산을 피하는 알고리즘인 것 같다.

 

내가 1열의 값을 구할 때 사용한게 슬라이딩 윈도우인가? 중복되는 계산을 뺀 것 같긴한데...?

뭔지 모르는 내가 풀어도 풀리는걸 보면 문제에서 슬라이딩 윈도우가 중요해보이지는 않는다.

 

다른 사람들의 코드를 보니 최대, 최소를 누적해서 구하신 분도 있었다.