백준 2096번 내려가기

< 백준 2096번 내려가기 - 마포 코딩박>

사용한 알고리즘: ..?


 한 행에 3칸씩 N 행이 주어지고, 각 칸에는 0~9까지의 수가 주어집니다.
1행부터 N행까지 주어진 규칙을 따라 내려가며 얻을 수 있는 최대, 최소 값을 구하는 문제였습니다.

문제풀이는 다음과 같습니다.
(1) (코드 6~8)
 입력으로 주어지는 3칸을 저장할 변수 one, two, three 와 경로를 따라 저장될 최대, 최소 값을 저장할 maxi1~3, mini1~3 를 지정해줍니다.

(2) (코드 17~42)
 N 번에 걸쳐 3칸씩 주어지면, mini1~3와 maxi1~3 값을 최신화 해줍니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int mod = 1000000;
	int N;
	int one, two, three;
	int maxi1, maxi2, maxi3;
	int mini1, mini2, mini3;
	int temp1, temp2, temp3;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	#endif // ONLINE_JUDGE
	cin >> N;
	for (int i = 0; i < N; ++i){
	cin >> one >> two >> three;
	if(i==0){
	maxi1 = one;
	maxi2 = two;
	maxi3 = three;
	mini1 = one;
	mini2 = two;
	mini3 = three;
	}
	else{
	temp1 = maxi1;
	temp2 = maxi2;
	temp3 = maxi3;
	maxi1 = one + max(temp1,temp2);
	maxi2 = two + max(temp3,max(temp1,temp2));
	maxi3 = three + max(temp2,temp3);
	temp1 = mini1;
	temp2 = mini2;
	temp3 = mini3;
	mini1 = one + min(temp1,temp2);
	mini2 = two + min(temp1,min(temp2,temp3));
	mini3 = three + min(temp2, temp3);
	}
	}
	cout << max(max(maxi1,maxi2),maxi3) << ' ' << min(min(mini1,mini2),mini3) << '\n';
	return 0;
	}

view raw BOJ 2096.cpp hosted with ❤ by GitHub