[백준 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; }
'⭐ 코딩테스트 > 백준' 카테고리의 다른 글
[백준 14503번 C/C++] 로봇 청소기 (0) | 2024.07.28 |
---|---|
[백준 17135번 C/C++] 캐슬 디펜스 (0) | 2024.07.25 |
[백준 13335번 C/C++] 트럭 (0) | 2024.07.21 |
[백준 16287번 C/C++] Parcel (0) | 2024.07.17 |
[백준 11401번 C/C++] 이항 계수 3 (0) | 2024.06.02 |
댓글
이 글 공유하기
다른 글
-
[백준 14503번 C/C++] 로봇 청소기
[백준 14503번 C/C++] 로봇 청소기
2024.07.28 -
[백준 17135번 C/C++] 캐슬 디펜스
[백준 17135번 C/C++] 캐슬 디펜스
2024.07.25 -
[백준 13335번 C/C++] 트럭
[백준 13335번 C/C++] 트럭
2024.07.21 -
[백준 16287번 C/C++] Parcel
[백준 16287번 C/C++] Parcel
2024.07.17
댓글을 사용할 수 없습니다.