[백준 17070] 파이프 옮기기 1

https://www.acmicpc.net/problem/17070 문제이해 파이프를 연결해서 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력 풀이 처음에는 DFS로 구해야겠다고 생각하고 문제에 나오는 조건들을 하나씩 보면서 구현했지만 Python3에서 시간초과가 발생했다. 그러나 PyPy3에서는 시간초과가 발생하지 않았고 인터넷을 찾아보니 C나 C++으로 DFS 구현해도 시간초과가 발생하지 않는다고 한다.

그러나 DP로 문제를 푸는 방법에 대한 글들을 보게 되었고 결국 더 빠르게 문제를 푸는 방법이 있기에 DP로 접근해서 풀어보았다. 처음으로 점화식을 생각할 때는 현재 파이프의 위치에서 다음 파이프의 위치를 고려해 수식을 정리하려 했다.

그러나 이런 방식은 DFS와 크게 다르지 않았다. 그래서 여러 사이트들을 참고한 결과 현재 파이프를 기준으로 이전 파이프에 대해서 생각을 하니 문제가 풀리기 시작했다. for i in range(1, N): for j in rang...