[BOJ] 4883번 : 삼각 그래프

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
const int val = 100005;
int d[val][4]; 
int a[val][4];
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t = 0;
	while (true) {
		t++;
		int n; 
		cin >> n; 
		if (n == 0) return 0; 
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= 3; j++) cin >> a[i][j];
		}

		d[1][1] = INT_MAX; 
		d[1][2] = a[1][2]; 
		d[1][3] = a[1][2] + a[1][3];
		for (int i = 2; i <= n; i++) {
			d[i][1] = min(d[i - 1][1], d[i - 1][2]) + a[i][1]; 
			d[i][2] = min({ d[i - 1][1],d[i - 1][2],d[i - 1][3],d[i][1] }) + a[i][2]; 
			d[i][3] = min({ d[i - 1][2],d[i - 1][3],d[i][2] }) + a[i][3]; 
		}
		cout << t << ". " << d[n][2] << '\n';
	}
}

dp를 이용해 풀었다. 따라서 세 가지 스텝을 따른다. 

1. 테이블을 정의한다. d [i][j] = i번째 행, j번째 열에서의 최솟값 

2. 점화식을 작성한다. 위 코드 참고 

3. 초기값을 설정한다. d [1][1] = INT_MAX, d [1][2] = a [1][2] , d [1][3] = a [1][2] + a [1][3]

 

상수로 표기할 수 있는 곳은 상수로 표기하자.