728x90
반응형
https://www.acmicpc.net/problem/17485
17485번: 진우의 달 여행 (Large)
첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다.
www.acmicpc.net
dfs로 탐색하면 어떨까 했는데 재귀로 1000*1000 =1000000정점을 탐색하는것을 시간/공간 복잡도 오류없이 해결할수 있을까 싶어서 dp로 풀었다. dfs,bfs 에 대한 시간/공간복잡도를 따로 정리해봐야겠다..
접근 방식
1. 맨처음 행으로 진입, 맨끝행에서 달로 갈때도 방향을 계산해야 하나 했는데 첫행은 값 자체를, 끝 행에 도착하면 모든 계산이 끝난것으로 가정
2. dp[i][j][dir] = (i,j) 방향으로 이전 블록에서 dir 방향으로 옴, 만약 이전 블록에서 아래로 내려가는 방향 ↓ 이었다면
dp[i][j][1]=min(dp[i-1][j][0],dp[i-1][j][2])+ arr[i][j] 가 된다.연속으로 같은 방향이되면 안되므로 (i-1,j) 으로는 이전에 ↓ 방향이 아닌 두 방향으로 와야 함
3. 양 끝의 열의 경우에는 두 방향에서만 올 수 있음
4. 마지막 행에서 dp 행렬을 모두 구했을때 각 좌표로 모든 방향이 왔을때 값들인 dp[n-1][j][0],dp[n-1][j][1],dp[n-1][j][2] 양수일 경우에만 비교하여 최소값을 탐색
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>>arr;
vector<vector<vector<int>>>dp;
arr.assign(n, vector<int>(m, 0));
dp.assign(n, vector<vector<int>>(m, vector<int>(3, 100000000)));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
}
}
for (int j = 0; j < m; j++) {
for (int k = 0; k < 3; k++) {
dp[0][j][k] = arr[0][j];
}
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j == 0) {//0,1
dp[i][j][0] = min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2])+arr[i][j];
dp[i][j][1] = min(dp[i - 1][j][0], dp[i - 1][j][2]) + arr[i][j];
}
else if (j == m - 1) {//1,2
dp[i][j][1] = min(dp[i-1][j][0],dp[i-1][j][2]) + arr[i][j];
dp[i][j][2] = min(dp[i-1][j-1][0],dp[i-1][j-1][1]) + arr[i][j];
}
else {
dp[i][j][0] = min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + arr[i][j];
dp[i][j][1] = min(dp[i - 1][j][0], dp[i - 1][j][2]) + arr[i][j];
dp[i][j][2] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + arr[i][j];
}
}
}
int mins = 100000000;
for (int a = 0; a < n; a++) {
for (int i = 0; i < m; i++) {
for (int k = 0; k < 3; k++) {
if (dp[n - 1][i][k])mins = min(mins, dp[n - 1][i][k]);
}
}
}
cout << mins;
}
728x90
반응형
'하루 1문제 챌린지 > Gold5' 카테고리의 다른 글
백준 10282번 해킹 (다익스트라,C++) (1) | 2024.06.17 |
---|---|
백준 1043번 거짓말(C++)🚩 (1) | 2024.02.27 |
백준 16562번 친구비(C++) 🚩 (0) | 2024.02.27 |
백준 203202번 민트초코(C++) 🚩 (1) | 2024.02.17 |
백준 14719번 빗물 (C++) 🚩 (0) | 2024.01.22 |