[ BOJ 백준 17070번 - 파이프 옮기기1 ] 해설 및 코드

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

 

목적

아래와 같이 밀어 파이프 끝을 (N,N)에 위치 시킬 수 있는 경우의 수를 구하자.

접근법

1. s[i][j][k]를 파이프의 방향이 k이고 끝이 (i, j)에 있을 때의 경우의 수로 정한다.

2. 방향에 따라 밀 수 있는 경우를 모두 검사하여 계산한다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
int n, a[16][16], s[16][16][3];
 
int sol(int i, int j, int dir) {
    if (i == j && i == n - 1) return 1;
    int& ref = s[i][j][dir];
    if (ref != -1)return ref;
 
    ref = 0;
    if (dir != 1 && j + 1 < n && !a[i][j + 1])ref += sol(i, j + 1, 0);
    if (dir != 0 && i + 1 < n && !a[i + 1][j])ref += sol(i + 1, j, 1);
    if (i + 1 < n && j + 1 < n && !a[i + 1][j] && !a[i][j + 1] && !a[i + 1][j + 1])ref += sol(i + 1, j + 1, 2);
    return ref;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(s, -1, sizeof(s));
    cin >> n;
    f(i, 0, n)f(j, 0, n)cin >> a[i][j];
    cout << sol(0, 1, 0);
    return 0;
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.