BOJ
BOJ::17069 파이프 옮기기 2
BOJ Gold 5
BOJ::17069 파이프 옮기기 2
- Link : BOJ::17069
- Level : Gold 5
- tag : dynamic programming
시사점
- 기본 DP 문제입니다.
- 주어지는 N이 32이므로, dfs/bfs 로는 TLE를 받을 것 같습니다.
이해(3)
- 파이프 옮기기1 과 같은 문제이지만, N의 범위가 32로 증가하였습니다.
- 물론 파이프 옮기기1도 DP로 풀 수 있지만, 해당 문제는 dfs로 풀었었습니다.
- (1,2)에 가로로 놓인 파이프의 한쪽 끝이 놓여져 있고,
- (n,n)에 도착할 수 있는 모든 경우의 수를 출력합니다.
설계, 손 코딩(1)
- 손으로 중심이 되는 코드를 구현합니다.
- DP 문제는 보통 경우의 수가 매우 많아서, long long을 주로 사용합니다.
- 해당 문제도 int형을 벗어나는 답이 도출됩니다.
- dp[ x ][ y ][i] : i모양으로 x,y에 올 수 있는 경로의 갯수
시간 복잡도
- O(N^2 * 3)
공간 복잡도
손 코딩 후 문제 리뷰(x)
- 빼먹고 손 코딩 한 것이 있는지 확인합니다.
구현(13)
함수 List
업데이트 되는 변수
- 대부분의 디버깅 문제는 업데이트 되는 변수에서 발생합니다.
실제 구현
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
const int MAXN = 32+4, MAXSTATUS = 3;
using namespace std;
typedef long long ll;
int n;
int a[MAXN][MAXN];
ll dp[MAXN][MAXN][MAXSTATUS];
void process(){
cin >> n; rep(i, 1, n+1) rep(j, 1, n+1) cin >> a[i][j];
dp[1][2][0] = 1;
rep(i, 1, n+1){
rep(j, 1, n+1){
if(a[i][j+1] != 1) dp[i][j+1][0] += dp[i][j][0] + dp[i][j][2];
if(a[i+1][j] != 1) dp[i+1][j][1] += dp[i][j][1] + dp[i][j][2];
if(a[i+1][j] != 1 && a[i][j+1] != 1 && a[i+1][j+1] != 1) dp[i+1][j+1][2]+= dp[i][j][0] + dp[i][j][1] + dp[i][j][2];
}
}
cout << dp[n][n][0] + dp[n][n][1] + dp[n][n][2] << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
process();
return 0;
}
구현 후 코드리뷰 + 예제 돌려보기(x)
- 바로 예제를 넣어서 테스트 해보기 전에, 코드를 한 번 리뷰하고, 예제의 입력이 이런식으로 왔을때 전체 코드가 어떤 식으로 순차적으로 진행되는지 답은 잘 도출될 것 같은지 확인합니다.