[백준 17070] - 파이프 옮기기 1(DP) C++

문제

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

17070번: 파이프 옮기기 1

접근방법

DP를 이용해 풀었다.

분명히 맞는 거 같은데, 틀렸다고 나와서 한참 헤멨다.

알고보니 cache 배열의 범위가 틀렸었다.

 

단순히 n의 범위가 16까지라서 cache[16][16]으로 정의했는데,

내가 범위 체크를 함수 들어가기 전이 아니라

함수 들어가고 나서 하기 때문에,

16 크기의 house배열이 입력으로 들어오는 경우, cache 17을 접근하게 되는 일이 발생한다.

따라서 cache[17][17]으로 바꿔 정의해줌으로써 문제를 해결했다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

#define FOR(i, n) for (int i=0;i<(n);++i)
#define INF 987654321

int n;
int house[16][16];
int cache[3][17][17];
//파이프를 이동시키는 방법의 수
//state: 2면 세로 0이면 대각선 1이면 가로
int pipe(int y, int x, int state) {
    
    int& ret = cache[state][y][x];
    if (ret != -1) return ret;
    ret = 0;
    if (y >= n || x >= n || house[y][x] == 1) return ret;
    if (state == 0 && (house[y-1][x] == 1 || house[y][x-1] == 1)) return ret;
    if (y == n-1 && x == n-1) return ret = 1;

    ret = pipe(y+1, x+1, 0);
    
    if (state == 1 || state == 0) ret += pipe(y, x+1, 1);
    if (state == 2 || state == 0) ret += pipe(y+1, x, 2);

    return ret;
}

int main() {

    cin >> n;
    FOR(i, n) FOR(j, n) cin >> house[i][j];
    memset(cache, -1, sizeof(cache));
    cout << pipe(0, 1, 1) << '\n';
    return 0;
}

결과

DP로 먼제 풀었지만, 그냥 완전탐색으로 풀어도 성공이 떴다.

다만, 시간이 더 오래걸리긴 하다.

개선할 점

사소한 실수를 방지하는 것이 중요하다. 

배열의 범위를 신경쓰자.

 

특히 DP할 때, cache의 범위.

graph를 둘러싸고 있는 cache까지 생각해야하는 경우,

cache의 크기는 graph보다 한 칸 커야 한다.