[백준] 17069번: 파이프 옮기기2 (C++ 풀이)

문제 https://www.acmicpc.net/problem/17069

풀이

블로그 풀이를 보았다...

파이프 옮기기1과 같은 문제인데 범위만 다른 문제이다

파이프 옮기기1은 N이 16까지라면 이것은 32까지다. 같은 코드를 제출했더니 메모리초과가 떴다.

DFS+DP 방법으로 풀었다.

dp는 3차원 long long 배열이다. 예제를 보면 출력 답이 int 범위를 넘는 것을 알 수 있다.

dp[a][b][c] = d의 의미 : (a, b)에서 c방향으로의 탐색을 했는데 (n-1, n-1)까지 갈 수 있는 경우의 수가 d이다.

dp값을 -1로 초기화해놓는다. 그 이유는 -1이 아직 방문하지 않음을 뜻하고

0은 목적지에 갈 수 있는 경우가 없다는 뜻!

목적지에 도착하면 1을 리턴한다! 그러면 재귀가 순서대로 빠지면서 경로에 있는 dp값들이 +1씩 된다.

dp값이 -1이면 방문하는 식으로 재귀를 하다가, dp값이 -1이 아닌 곳을 만나면 그 값을 리턴한다.

왜냐하면 그 이후로는 갈 필요가 없기 때문!

코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/17069.cpp

결과