[백준OJ] 2096번 내려가기

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

2096번: 내려가기

---

 

-풀이-

DP를 이용하여 문제를 풀었다.

최대와 최소는 min, max만 따로 구별하면 되므로, max를 예로 들어보겠다.

현재까지 첫번째 칸, 두번째칸 , 세번째 칸까지 최고비용을 ma[0],ma[1],ma[2] 에 담았다고 하자.

다음칸으로 내려갈때, 다음칸의 첫번째칸, 두번째칸, 세번째칸의 최대비용은 어떻게 구할까?

 

이런식으로 존재한다 했을때, a로 갈 수 있는 칸은 1번칸과 2번칸이다. 따라서 다음 1번칸(ma[0]) 을 갱신해주기위해, a`과 b`중 큰 값을 a와 더해서 ma[0]에 넣어주어야한다.

 

b로 갈 수 있는 칸은, 1번 2번 3번 모두다이다. 2번칸(ma[1]) 을갱신해주기 위해서 a`,b`,c`중 제일 큰값을 구해 b와 더해서 ma[1]에 넣어주어야 한다.

 

c로 갈 수 있는 칸은 2번,3번칸이다. 따라서 3번칸(ma[2])을 갱신해주기 위해서는 b`과 c`중 큰값을 구해 c와 더해서 ma[2]에 넣어주어야 한다.

 

이때, 계산하기전에 각 a` , b` , c` 을 뽑아서 임시변수에 저장을 해야한다. 왜냐하면 1번칸을 갱신하면, 2번칸을 계산할때, 갱신된 1번칸의 값이 적용되기때문이다. 

 

마지막 층까지 계산을 마치면, 1번칸 2번칸 3번칸 중 제일 큰 값을 출력해주면 된다.

 

최솟값은 반대로 해주면 된다.

 

-시간복잡도-

각층마다 단순계산이므로, O(N)이된다.

 

-코드-

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int mi[3], ma[3];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (i == 0) {
			mi[0] = ma[0] = a;
			mi[1] = ma[1] = b;
			mi[2] = ma[2] = c;
		}
		else {
			int t1 = mi[0], t2 = mi[1],t3=mi[2];
			mi[0] = min(t1 + a, t2 + a);
			mi[1] = min(t1 + b, min(t2 + b, t3 + b));
			mi[2] = min(t2 + c, t3 + c);

			t1 = ma[0];
			t2 = ma[1];
			t3 = ma[2];
			ma[0] = max(t1 + a, t2 + a);
			ma[1] = max(t1 + b, max(t2 + b, t3 + b));
			ma[2] = max(t2 + c, t3 + c);
		}
	}
	cout << max(ma[0], max(ma[1], ma[2])) << " " << min(mi[0], min(mi[1], mi[2])) << "\n";
	return 0;
}