모든 챌린지
보통 1명 해결 정답률 25.0%

주사위 수열 개수 세기

주어진 합을 가지는 순서 있는 주사위 던지기 수열의 개수를 세세요.

배우게 될 내용

  • 작은 합에서 답 쌓아 올리기
  • 마지막 주사위 값으로 점화식 쓰기
  • 큰 소수로 나눈 나머지 구하기

문제

원문 보기 (영어)

표준 주사위는 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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

# 코더 언어 시간 메모리 AI 평가 풀이
1 ННикита Python 973 ms - 5/5 코드 보기

다른 사람의 풀이 보기

커뮤니티 솔루션

스포일러: 아래에 1개 전체 솔루션 있음 먼저 직접 풀어보세요. 다른 개발자의 코드와 AI 리뷰도 참고할 수 있습니다. 로그인하고 문제를 풀면 토론에 참여할 수 있습니다.