백준 No.2008 [사다리 게임]

백준 No.2008 [사다리 게임]

---

  문제 

2008번: 사다리 게임 (acmicpc.net)

2008번: 사다리 게임

---

  설명 

 <알고리즘 분류> 
 * dp

  2차원 dp 를 이용하여 풀이가 가능하다.

  

  dp[i][k]  :  i 번째 가로선까지 체크를 했을 때 시작점에서 k 번째 세로선까지 오기까지의 최소비용

 

  위 값을 결정하기 위해선 이전 dp 값의 왼쪽, 현재 위치, 오른쪽 인 dp[i - 1][k - 1], dp[i - 1][k], dp[i - 1][k + 1] 을 고려한다.

---

1)  dp[i - 1][k - 1] 을 고려하는 경우

Case) A 는 연결된 가로선이 있는 경우, Case) B 는 연결된 가로선이 없어서 가로선을 만들어야 하는 경우이다.

 

Case) A : dp[i][k] = dp[i - 1][k - 1] ;

Case) B : dp[i][k] = dp[i - 1][k - 1] + make_cost ;

 

---

2)  dp[i - 1][k] 을 고려하는 경우

Case) A 는 연결된 가로선이 없는 경우, Case) B 는 연결된 가로선이 있어서 가로선을 지워야 하는 경우이다.

 

Case) A : dp[i][k] = dp[i - 1][k - 1] ;

Case) B : dp[i][k] = dp[i][k], dp[i - 1][k - 1] + delete_cost ;

 

---

3)  dp[i - 1][k + 1] 을 고려하는 경우

Case) A 는 연결된 가로선이 있는 경우, Case) B 는 연결된 가로선이 없어서 가로선을 만들어야 하는 경우이다.

  이전에 dp[i - 1][k - 1] 을 고려하는 경우와 좌우만 대칭이다.

 

Case) A : dp[i][k] = dp[i - 1][k + 1] ;

Case) B : dp[i][k] = dp[i - 1][k + 1] + make_cost ;

 

---

 

  위 6개의 경우들을 확인하면서 가장 min 값을 뽑으면 된다.

 

  이 때, 가장 마지막 가로선인 m 번째 가로선을 체크한 뒤에 한번 더 체크를 해야한다. 마지막 가로선을 통해 어딘가의 세로선에서 현재 비용보다 더 적은 비용을 뽑을 수 있는 경우가 존재할 수 있기 때문이다.

 

 <정리> 
1. 2 차원 dp 를 통해 풀 수 있다.
2. 현재의 dp 값을 체크할 때, 현재 세로선과 연결된 가로선이 있는지 여부도 따져야한다.

---

  Code 

#include <iostream>
#include <vector>

#define N 101
#define M 501
#define inf 999999

using namespace std;

int n, m;
int s, e;
int delCost, makeCost;
int arr[M + 1];
int dp[M + 1][N];

inline bool has_row(int& cur_line, int& cur) {
	return cur_line == cur || cur_line + 1 == cur;
}

inline bool has_right_row(int& cur_line, int& cur) {
	return cur_line == cur;
}

inline bool has_left_row(int& cur_line, int& cur) {
	return cur_line + 1 == cur;
}

int solve() {
	int cur_line = arr[1];

	// 가로선이 없는 경우
	if (!cur_line) {
		for (int cur = 1; cur <= n; cur++)
			dp[0][cur] = makeCost * abs(s - cur);
		return dp[0][e];
	}

	// dp[1][k] 값들에 대한 초기화
    // dp[1][k] 값들은 시작점 으로부터의 최소 비용을 계산해야 하므로
    // 따로 코드를 짰다.
	for (int cur = 1; cur <= n; cur++) {
		if (cur == s) continue;

		if (cur_line < s) {
			if (cur < s) {
				if (cur <= cur_line) dp[1][cur] = makeCost * (s - cur - 1);
				else dp[1][cur] = makeCost * (s - cur);
			}
			else if (s < cur) dp[1][cur] = makeCost * (cur - s);
		}
		else if (s <= cur_line) {
			if (s < cur) {
				if (cur_line < cur) dp[1][cur] = makeCost * (cur - s - 1);
				else dp[1][cur] = makeCost * (cur - s);
			}
			else if (cur < s) dp[1][cur] = makeCost * (s - cur);
		}
	}

	if (cur_line == s || cur_line + 1 == s) {
		dp[1][s] = delCost;
		if (cur_line == s) dp[1][s] = min(dp[1][s], dp[1][s + 1] + makeCost);
		else dp[1][s] = min(dp[1][s], dp[1][s - 1] + makeCost);
	}
	
	for (int i = 2; i <= m + 1; i++) {
		cur_line = arr[i];

		for (int cur = 1; cur <= n; cur++) dp[0][cur] = dp[1][cur];

		for (int cur = 1; cur <= n; cur++) {
			// 위에서 갖고오는데 지금 이 ladder에 가로선이 있으면 delCost 고려해야한다.
			dp[1][cur] = dp[0][cur] + (has_row(cur_line, cur) ? delCost : 0);

			// cur 세로선이 1 보다 크면 왼쪽 값을 고려한다.
			if (1 < cur)
				dp[1][cur] = min(dp[1][cur]
					, dp[0][cur - 1] + (has_left_row(cur_line, cur) ? 0 : makeCost));
                    
			// cur 세로선이 n 보다 작으면 오른쪽 값을 고려한다.
			if (cur < n)
				dp[1][cur] = min(dp[1][cur]
					, dp[0][cur + 1] + (has_right_row(cur_line, cur) ? 0 : makeCost));
		}
	}

	return dp[1][e];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n >> m;
	cin >> s >> e >> delCost >> makeCost;

	for (int i = 1; i <= m; i++)
		cin >> arr[i];
	arr[m + 1] = inf;

	cout << solve();
}