[백준 1146번] 지그재그 서기 (Python3)

def DFS(n,now):
  if not (N-n)%2:
    for next in range(now,n):
      if not DP[n-1][next]:
        DFS(n-1,next)
      DP[n][now] += DP[n-1][next]
  else:
    for next in range(now):
      if not DP[n-1][next]:
        DFS(n-1,next)
      DP[n][now] += DP[n-1][next]
  DP[n][now] %= 10**6

N = int(input())
if N==1:
  print(1)
else:
  DP = [[1]]+[[0]*N for i in range(N)]
  DFS(N,0)
  print(2*DP[N][0]%10**6)

간단한 DP 문제

DP를 어떻게 설정할지가 가장 중요하며, 구현은 매우 쉽다.

 

알고리즘을 설명하면,

1. DP를 N*N 배열로 두고, DP[n][now]를 "현재 숫자가 남아있는 숫자들 중 now번째 숫자일 때 n개의 숫자를 지그재그로 채우는 경우의 수" 로 두었다.

2. 그리고 현재가 짝수번째인 경우, now보다 작은 숫자들을 next로 두고, 홀수번째인 경우, now보다 크거나 같은 숫자부터 n까지를 next로 둔다. (같은 경우가 성립하는 이유는 next"번째" 이기 때문이다. 예를 들어 남은 숫자가 1,2,3인데 now가 2라면, next는 1,3 중 두번째로 큰 수인 3이 된다)

3. N이 1인 경우 1을 출력, N이 2 이상인 경우 구한 경우의 수 *2개를 출력한다.

 

3번에서 구한 경우의 수에 *2를 하는 이유는 맨 처음에 작아지면서 시작하는 것과 커지면서 시작하는 경우의 수를 모두 구해야하기 때문이다. 이때 두 경우의 수가 같다고 둘 수 있는 이유는, 만약 N이 3이라면 1 3 2, 2 3 1이 있다고 쳤을 때, 모든 숫자를 N+1에서 뺀 새로운 수열을 생각하면 된다.

4-1 4-3 4-2 = 3 1 2, 4-2 4-3 4-1 = 2 1 3

즉 커지면서 시작하는 지그재그 수열을 N+1에서 뺀 수열이 곧 작아지면서 시작하는 지그재그 수열이다. 다만 1의 경우 경우의 수가 2가 아닌 1이기 때문에 예외처리를 한다.

 

참고로 나머지 처리에 주의해야 한다. DFS 중에만 나머지처리를 하고 마지막 결과값을 출력할 때 2배를 한 다음 나머지처리를 하지 않으면 틀리게 된다. (이거때문에 애먹었다)

 

 

오늘의 교훈) 나머지처리 항상 조심