728x90
반응형
https://www.acmicpc.net/problem/17484
1. Logic
브루트 포스로 풀 수 있지만 각 칸에서의 최솟값은 변하지 않기 때문에 그 값을 저장해 놓고 DP로 풀이할 수 있다.
2. Code
#include <bits/stdc++.h>
using namespace std;
int n, m;
int space[10][10];
int dp[10][10][4];
//0:왼 1:dir 2:오
int solve(int y, int x, int prev) {
if(y == n) return 0;
int &ret = dp[y][x][prev];
if(ret != -1) return ret;
ret = 0x3f3f3f3f;
if(x-1 >= 0 && prev != 0) {
ret = min(ret, solve(y+1, x-1, 0) + space[y][x]);
}
if(x+1 < m && prev != 2) {
ret = min(ret, solve(y+1, x+1, 2) + space[y][x]);
}
if(prev != 1) {
ret = min(ret, solve(y+1, x, 1)+space[y][x]);
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
memset(dp, -1, sizeof(dp));
cin >> n >> m;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> space[i][j];
}
}
int ans = 0x3f3f3f3f;
for(int i = 0; i < m; i++) {
ans = min(ans, solve(0, i, 3));
}
cout << ans;
}
알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐
728x90
반응형
'Algorithm > Beakjoon' 카테고리의 다른 글
[백준/Baekjoon] 25757 임스와 함께하는 미니게임 C++ :: Data structure (1) | 2023.11.21 |
---|---|
[백준/Baekjoon] 4673 셀프 넘버 C++ :: Implementation & Brute force (1) | 2023.11.20 |
[백준/Baekjoon] 1939 중량제한 C++ :: Binary Search & BFS (0) | 2023.11.17 |
[백준/Baekjoon] 1253 좋다 C++ :: Two pointer (2) | 2023.11.17 |
[백준/Baekjoon] 17503 맥주 축제 C++ :: Data structure & Binary Search (0) | 2023.11.16 |