백준 17070번 파이프 옮기기 1 ( C++ )

문제

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

 

해설

경우의 수가 16 * 16 * 3 이기 때문에 그냥 탐색으로 해결

경우의 수가 더 커질 경우 DP를 이용해야함

 

코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int n, ret, mp[20][20];
 
void go(int y, int x, int ty){
  if(y == n-1 && x == n-1){
    ret++;
    return;
  }
  
  if(ty != 1){
    if(x+1 < n && mp[y][x+1] == 0){
      go(y,x+1,0);
    }
  }
 
  if(ty != 0){
    if(y+1 <n && mp[y+1][x] == 0){
      go(y+1,x,1);
    }
  }
 
  if(x+1<n && y+1 <n && mp[y][x+1] == 0 && mp[y+1][x] == 0 && mp[y+1][x+1] == 0){
    go(y+1,x+1,2);
  }
}
 
int main(){
  cin >> n;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin >> mp[i][j];
    }
  }
 
  go(0,1,0);
  cout << ret;
  return 0;
}