문제
There are n uniquely-sized sticks whose lengths are integers from 1 to n. You want to arrange the sticks such that exactly k sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it.
For example, if the sticks are arranged [1,3,2,5,4], then the sticks with lengths 1, 3, and 5 are visible from the left.
Given n and k, return the number of such arrangements. Since the answer may be large, return it modulo 109 + 7.길이가 모두 서로 다른 막대기 n개가 있습니다. 각 막대기의 길이는 1부터 n까지의 정수입니다.
이 막대기들을 일렬로 배치하려고 합니다. 이때 왼쪽에서 보이는 막대기가 정확히 k개가 되도록 배치해야 합니다.
어떤 막대기의 왼쪽에 그 막대기보다 더 긴 막대기가 하나도 없다면, 그 막대기는 왼쪽에서 보인다고 합니다.
예를 들어 막대기들이 다음과 같이 배치되어 있다고 합시다.
[1, 3, 2, 5, 4]이 경우 길이가 1, 3, 5인 막대기들이 왼쪽에서 보입니다.
정수 n과 k가 주어질 때, 조건을 만족하는 막대기 배치의 개수를 반환하세요.
정답이 매우 클 수 있으므로, 10^9 + 7로 나눈 나머지를 반환하세요.
예시
입력: n = 3, k = 2
출력: 3
설명: 왼쪽에서 보이는 막대기가 정확히 2개가 되도록 배치하는 경우는 다음 세 가지뿐입니다.
[1, 3, 2]
[2, 3, 1]
[2, 1, 3]제한
풀이
해당 문제에 주어진 상태는 총 두개이다.
- n : 배치할수 있는 모든 막대의 갯수 ( 1~n의 길이이며 같은것은 없다 )
- k : 왼쪽에 보여야 하는 갯수
만약 n개의 막대중 가장 작은것 하나를 가장 왼쪽에 배치한다면 나머지 n-1개의 막대중 k-1개를 왼쪽에서 보이게 하는 경우가 남는다.
- dp[n-1][k-1]
만약 n개의 막대중 가장 작은것 하나를 남은 막대들 사이에 넣을 경우 가능한 위치는 n-1개가 될 것이며 k개의 막대를 왼쪽에서 보이게 해야 한다.
- (n - 1) * dp[n-1][k]
n개의 막대중 가장 큰것은 반드시 왼쪽에서 보여야 하기 때문에 남은 스틱의 갯수와 보여야하는 갯수가 둘다 0일때에만 가능한 경우가 된다.
보여야 하는 갯수가 먼저 0이 되거나 ( 놓지 않은 막대가 있음 ) 보여야 하는 막대가 전체 막대보다 많은 경우도 불가능하다.
이를 Top down DP로 구현시
class Solution:
def rearrangeSticks(self, n: int, k: int) -> int:
MOD = 10**9 + 7
@cache
def dp(n: int, k: int) -> int:
if n == 0:
return 1 if k == 0 else 0
if k == 0 or k > n:
return 0
return (dp(n - 1, k - 1) + (n - 1) * dp(n - 1, k)) % MOD
return dp(n, k)이 되고
Bottom up DP로 구현시
class Solution:
def rearrangeSticks(self, n: int, k: int) -> int:
MOD = 10**9 + 7
dp = [[0] * (k + 1) for _ in range(n + 1)]
for stick in range(n + 1):
for visible in range(k + 1):
if stick == 0 and visible == 0:
dp[stick][visible] = 1
elif visible != 0 and visible <= stick:
dp[stick][visible] = (dp[stick - 1][visible - 1] + (stick - 1) * dp[stick - 1][visible]) % MOD
return dp[-1][-1]가 된다.
