[ 백준 1670 해설 ] ( python ) 정상 회담2

📚 정상 회담2

문제 설명

여러 개의 소국가로 나뉘어져 있었던 A국을 다시 하나의 국가로 합치기 위해 각 소국가의 대표 N명이 원탁에 모였다.

각 대표는 미리 원탁의 자리를 배정받았다. 회의를 시작하기 전에 일단 서로 악수를 하려고 한다. 각 대표는 한 사람과만 악수할수 있고, 모든 악수는 동시에 일어난다. 이때, 어떤 사람의 팔도 교차하지 않았을 때 완벽하게 악수했다고 한다.

N이 주어지면 완벽하게 악수하는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정상 회담에 참가한 사람의 수 N이 주어진다. 이 값은 10,000보다 작거나 같은 짝수이다.

출력

완벽한 악수의 경우의 수를 987654321로 나눈 나머지를 출력한다.

예제 입력 1

4

예제 출력 1

2

 

 

예제 입력 2

2

예제 출력 2

1

예제 입력 3

8

예제 출력 3

14

 

 

✍ 접근

dp로 접근했다. 점화식을 세우는게 어려웠다.

무엇보다.. 계속 시간초과가 났다 😵

 

 

 

정답코드 

import sys
input = sys.stdin.readline

N = int(input())

dp = [0]*(N+1)
div = 987654321

dp[0] = 1
dp[2] = 1

for i in range(4,N+1,2): # dp채우기
    plus = 0
    for j in range(0,i//2,2): # 내부 돌기 (중간까지만)
        left = j
        right = i-j-2
        if left != right:
            plus += dp[left]*dp[right]*2
        else:
            plus += dp[left]*dp[right]
    dp[i] = plus % div # ✨✨

print(dp[N])

해설

• 핵심은 도형을 한 악수를 기준으로 원탁을 쪼개는 것이다
  • 8명이 있을 때, 1번과 4번이 악수를 한다면 원탁은 2명과 4명으로 쪼개진다
  • 8명이 있을 때, 1번과 2번이 악수를 한다면 원탁은 0명(악수 기준 오른쪽)과 6명(악수 기준 왼쪽)으로 쪼개진다
• for문을 돌면서 원탁에 사람이 2명씩 늘어날 때 사람의 수(i)를 구한다
• 두번째 for문을 통해 원탁을 쪼개준다.
  • 짝수로 쪼개는 이유는, 겹치지 않는 악수는 left(악수 기준 왼쪽) right(악수 기준 오른쪽) 모두 짝수일 때 가능하기 때문이다
  • 만약 왼쪽과 오른쪽이 같을 때 (6명이 앉았을 때 악수 기준 왼쪽(2명) 오른쪽(2명)이 되거나, 10명이 앉았을 때 악수 기준 왼쪽(4명) 오른쪽(4명)이 될 때)는 원탁에서 한번밖에 등장하지 않음으로 2를 곱하지 않는다.
  • 그게 아닐 때(원탁에 앉은 사람들이 4의 배수일 때)는 관계없다

 

 

 

 

⭐ 배움

• 오랜만에 알고리즘 글을 쓴 이유는, 정말 큰 수가 등장했을 때 그를 계산한다는 것 자체가 시간초과에 영향을 줄 수 있다는 것을 알았기 때문이다.
• 큰 수로 나눠서 나머지를 제출하라는 문제는, 중간중간 꾸준히 수를 나눠주면서 시간초과 가능성을 없애자