💻 백준 8394: 악수

문제 소개 🧐

회의에 참석한 N명의 사람들이 일렬로 앉아있다. 각 사람은 자신의 왼쪽 또는 오른쪽에 있는 사람과 악수할 수 있고, 안 할 수도 있다. 이때, 모든 사람이 악수하는 방법의 총 경우의 수를 구하는 문제다. 단, 팔이 교차되면 안 된다.

입력 📝

첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다.

출력 📤

악수하는 방법의 수를 10으로 나눈 나머지를 출력한다.

제한 ❌

  • 시간: 1초
  • 메모리: 128 MB

나의 풀이: 피보나치 수열의 발견! 🎉

Idea

이 문제는 점화식을 세워 해결할 수 있는 다이나믹 프로그래밍 문제였다. N번째 사람이 악수하는 경우의 수를 dp[n]이라고 정의하고 규칙을 찾아보았다.

1) n번재 사람이 악수 안한 경우는 n-1번째 사람의 악수여부와 상관없이 무조건 올 수 있음 -> dp[n-1] 경우
2) n번째 사람이 왼쪽 사람과 악수한 경우는 n-1번째 사람은 무조건 악수 안한 상태여야 함 -> dp[n-2] 경우

규칙을 살펴보니 dp[n] = dp[n-1] + dp[n-2] 라는 피보나치 수열의 점화식이 성립하는 것을 발견했다.

N이 매우 크기 때문에, 반복문을 사용하여 피보나치 수를 계산하고, 결과는 10으로 나눈 나머지만 저장하여 메모리와 시간 효율을 높였다.

Code

import sys

n = int(sys.stdin.readline().rstrip())
dp = [0] * (n+1)

dp[1] = 1  # 초기화
dp[2] = 2

for i in range(3, n+1):
    dp[i] = dp[i-1]%10 + dp[i-2]%10

print(dp)

Result

성공! ✅

피보나치 수열 점화식을 통해 DP로 문제를 해결했다.

배운 점 및 느낀 점 ✍️

  • 규칙 찾기: 복잡해 보이는 경우의 수 문제도, 작은 N부터 차례대로 경우의 수를 나열해보면 숨겨진 규칙이나 점화식을 발견할 수 있다는 것을 깨달았다.
  • 피보나치 수열의 응용: 악수 문제와 같이 전혀 관련 없어 보이는 문제도 피보나치 수열로 모델링될 수 있다는 점이 흥미로웠다.
  • 메모리 최적화: N이 천만까지 가능하므로 DP 배열을 모두 만드는 것은 비효율적이다. 현재 값을 계산하는 데 이전 두 개의 값만 필요하므로, 변수 두 개만 사용하여 공간 복잡도를 O(1)로 최적화할 수 있었다.