[백준 13335번 C/C++] 트럭

 

[백준 13335번 C/C++] 트럭

 

 

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

---

 

 

해결전략

 

동적 계획법 Dynamic Programming, DP

 

---

 

 

정답코드

 

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

int n;
vector<vector<int>> v, result;
int dp[16][16][3]; // 0: 가로, 1: 세로, 2: 대각선

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

	cin >> n;
	v.resize(n, vector<int>(n));
	result.resize(n, vector<int>(n));
	for (int y = 0; y < n; y++){
		for (int x = 0; x < n; x++) {
			cin >> v[y][x];
		}
	}

	dp[0][1][0] = 1; // 시작 위치(문제 조건)
	for (int i = 2; i < n; i++) {
		if (v[0][i] == 1){ // 벽O
			dp[0][i][0] = 0;
		}
		else{ // 벽X
			dp[0][i][0] = dp[0][i-1][0];
		}
	}

	for (int y = 1; y < n; y++) {
		for (int x = 1; x < n; x++) 
		{
			if (v[y][x] == 1) { // 벽O
				dp[y][x][0] = 0;
				dp[y][x][1] = 0;
				dp[y][x][2] = 0;
			}
			else { // 벽X
				dp[y][x][0] = dp[y][x - 1][0] + dp[y][x - 1][2]; // 가로 방향
				dp[y][x][1] = dp[y - 1][x][1] + dp[y - 1][x][2]; // 세로 방향

				// 대각선 방향, 대각선으로 오기 전 칸들이 모두 벽이 아닐 경우에만 가능
				if (v[y-1][x] == 0 && v[y][x-1] == 0)
				{
					dp[y][x][2] = dp[y - 1][x - 1][0] + dp[y - 1][x - 1][1] + dp[y - 1][x - 1][2];
				}
			}
		}
	}

	// (n-1, n-1) 위치에 도달하는 모든 경우의 수
	cout << dp[n-1][n-1][0] + dp[n - 1][n - 1][1] + dp[n - 1][n - 1][2] << "\n";

	return 0;
}

 

---