값 h와 블랙리스트라는 숫자 목록이 있다고 가정합니다. 우리는 현재 높이 h에 있고 작은 공을 높이 0으로 옮기는 게임을 하고 있습니다. 이제 짝수 라운드(0부터 시작)에서 공을 1, 2 또는 4 계단 아래로 이동할 수 있습니다. 홀수 라운드에서는 공을 1, 3, 4계단 아래로 이동할 수 있습니다. 일부 레벨은 블랙리스트에 있습니다. 따라서 공이 거기에 도달하면 즉시 죽습니다. 공이 높이 0에서 아래로 이동할 수 있는 방법의 수를 찾아야 합니다. 답이 너무 크면 결과를 10^9 + 7로 수정합니다.
따라서 입력이 h =5 블랙리스트 =[2, 1]과 같으면 출력은 2가 됩니다. 왜냐하면 라운드 0에서 먼저 한 단계(5에서 4로) 이동한 다음 다음 라운드에서 4에서 0으로 이동하기 때문입니다. 다른 가능한 방법은 라운드 0에서 두 단계(5에서 3으로) 이동한 다음 다음 라운드에서 3에서 0으로 이동하는 것입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- blacklist :=블랙리스트 요소의 새로운 세트
- 0이 블랙리스트에 있거나 h가 블랙리스트에 있으면
- 0을 반환
- dp :=크기 h의 목록과 각 인덱스의 [0, 0] 쌍을 저장하는 내부
- dp[0] :=[1, 1]
- m :=10^9 + 7
- 1~h 범위의 i에 대해 다음을 수행합니다.
- [1, 2, 3, 4]의 각 x에 대해 다음을 수행합니다.
- i - x>=0이고 i - x가 블랙리스트에 없으면
- x가 3과 같지 않으면
- dp[i, 0] :=dp[i, 0] + dp[i - x, 1]
- x가 2와 같지 않으면
- dp[i, 1] :=dp[i, 1] + dp[i - x, 0]
- x가 3과 같지 않으면
- dp[i, 0] :=dp[i, 0] 모드 m
- dp[i, 1] :=dp[i, 1] 모드 m
- i - x>=0이고 i - x가 블랙리스트에 없으면
- [1, 2, 3, 4]의 각 x에 대해 다음을 수행합니다.
- 반환 dp[h, 0]
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(h, blacklist):블랙리스트 =set(블랙리스트) 블랙리스트에서 0 또는 블랙리스트에서 h:return 0 dp =[[0, 0] for i in range(h + 1)] dp[0] =[1, 1] m =10 ** 9 + 7 for i in range(1, h + 1):for x in [1, 2, 3, 4]:if i - x>=0 and i - x 블랙리스트에 없음:if x !=3:dp[i][0] +=dp[i - x][1] if x !=2:dp[i][1] +=dp[i - x][ 0] dp[i][0] %=m dp[i][1] %=m return dp[h][0]h =5blacklist =[2, 1]print(solve(h, blacklist))입력
5, [2, 1]출력
2