주사위 수열 개수 세기

문제

표준 주사위는 1부터 6까지의 정수를 생성합니다. 합이 target이 되는, 비어 있지 않은 모든 순서 있는 결과 수열의 개수를 세세요. 순서가 다르면 다른 수열로 간주합니다. 개수를 1,000,000,007로 나눈 나머지를 반환하세요.

dice_combinations(target)을 구현하세요.

target: 모든 주사위 던지기의 합으로 만들어야 하는 값입니다.

수열의 개수를 1,000,000,007로 나눈 나머지를 반환하세요.

1 ≤ target ≤ 1,000,000. 개수를 1,000,000,007로 나눈 나머지를 반환한다는 것은, 그 수를 1,000,000,007로 나눈 뒤의 나머지를 반환한다는 의미입니다.

예시 1

입력:
target = 2

예상 출력:
expected = 2

입력:
long long target = 2;

예상 출력:
long long expected = 2;

입력:
long target = 2;

예상 출력:
long expected = 2;

두 가지 수열은 [2]와 [1, 1]입니다.

예시 2

입력:
target = 4

예상 출력:
expected = 8

입력:
long long target = 4;

예상 출력:
long long expected = 8;

입력:
long target = 4;

예상 출력:
long expected = 8;

가능한 수열은 [4], [1,3], [3,1], [2,2], [1,1,2], [1,2,1], [2,1,1], [1,1,1,1]입니다.

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

작은 합들을 목표 합의 재료처럼 생각한다.

힌트 2

각 합은 바로 앞의 6개 합을 바탕으로 누적 개수를 구한다.

힌트 3

더할 때마다 modulo를 적용하고, 1보다 작은 합은 따로 처리한다.

예상 복잡도

시간 O(target), 추가 공간 O(target)

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.