문제 개요
수직선 위에 n개의 점이 있다고 가정해 보겠습니다. i번째 점(0부터 n-1까지)은 위치 x = i에 놓여 있습니다. 이때 각 선분이 두 개 이상의 점을 포함하도록 하면서, 정확히 k개의 서로 겹치지 않는 선분을 그릴 수 있는 경우의 수를 구해야 합니다.
각 선분의 양 끝점은 반드시 정수 좌표여야 하며, k개의 선분이 모든 n개의 점을 덮을 필요는 없습니다. 또한 선분끼리 끝점을 공유하는 것도 허용됩니다. 만약 답이 너무 커진다면 10^9 + 7로 나눈 나머지를 반환하면 됩니다.
예시
입력이 n = 4, k = 2라고 가정해 봅시다. 이 경우 출력은 5가 되며, 가능한 다섯 가지 조합은 다음과 같습니다.
[(0 ~ 2), (2 ~ 3)], [(0 ~ 1), (1 ~ 3)], [(0 ~ 1), (2 ~ 3)], [(1 ~ 2), (2 ~ 3)], [(0 ~ 1), (1 ~ 2)]
풀이 접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용해 해결할 수 있습니다. 핵심 아이디어는 각 '간격'을 순서대로 살펴보면서 세 가지 선택지, 즉 건너뛰기, 새 선분 시작, 기존 선분 이어 그리기를 재귀적으로 탐색하는 것입니다. 단계별 과정은 다음과 같습니다.
- 모듈로 연산에 사용할 값 m := 10^9 + 7을 설정합니다.
- n := n - 1로 조정합니다. 선분은 점 자체가 아니라 점과 점 사이의 간격을 기준으로 정의되기 때문입니다.
- 세 개의 매개변수, 즉 현재 위치 i, 진행 중인 선분의 존재 여부 covered, 완성된 선분의 개수 j를 받는 dp() 함수를 정의합니다.
- i가 n과 같으면 모든 간격을 확인한 것이므로, j가 k와 같을 때만 참(1)을 반환하고 그렇지 않으면 거짓(0)을 반환합니다.
- j가 k보다 크면 이미 선분 개수를 초과했으므로 유효하지 않은 상태이며 0을 반환합니다.
- ans := dp(i + 1, False, j) + dp(i + 1, True, j + 1) — 현재 간격을 건너뛰는 경우와 그 간격에서 새 선분을 시작하는 경우를 더합니다.
- covered가 참이라면 기존 선분을 이어 그릴 수도 있으므로 ans := ans + dp(i + 1, True, j)를 추가합니다.
- 마지막으로 ans mod m을 반환합니다.
메인 함수에서는 dp(0, False, 0)을 호출하여 전체 경우의 수를 얻습니다.
예제 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
def solve(n, k):
m = 10 ** 9 + 7
n -= 1
def dp(i, covered, j):
if i == n:
return j == k
if j > k:
return 0
ans = dp(i + 1, False, j) + dp(i + 1, True, j + 1)
if covered:
ans += dp(i + 1, True, j)
return ans % m
return dp(0, False, 0)
n = 4
k = 2
print(solve(n, k))입력
4, 2
출력
5
성능 개선 팁
위 구현은 순수 재귀 방식이므로 n이 커지면 중복 계산이 많아질 수 있습니다. functools.lru_cache 데코레이터를 dp 함수에 적용하거나, 재귀를 반복문 기반 DP 테이블로 변환하면 불필요한 연산을 제거해 실행 속도를 크게 향상시킬 수 있습니다.