울타리 이어 붙이기

300점케이스 15출제 dongbinna

10월 30일에 올라온 문제입니다.

문제

한 마을에는 1번부터 N번까지 번호가 붙은 공방 N곳이 있다. 각 공방은 널빤지를 여러 장 가지고 있고, 한 공방이 가진 널빤지는 최대 M장이다. 널빤지마다 길이가 다를 수 있다.

마을 사람들은 공방을 돌며 널빤지를 모아 울타리 한 줄을 만들려고 한다. 널빤지는 1번 공방부터 N번 공방까지 차례대로 받아서 받은 순서대로 이어 붙인다. 한 공방에서는 널빤지를 최대 한 장만 받을 수 있고, 아무것도 받지 않고 지나가도 된다.

같은 공방이 길이가 같은 널빤지를 여러 장 가지고 있을 수도 있다. 이때 길이가 같아도 서로 다른 널빤지이므로, 어느 널빤지를 받았는지에 따라 서로 다른 방법으로 센다.

울타리의 전체 길이가 정확히 H가 되도록 널빤지를 받는 방법이 몇 가지인지 계산하는 프로그램을 작성하여라. 방법의 수가 매우 커질 수 있으므로 방법의 수를 10,007로 나눈 나머지를 출력한다.

예를 들어 N=3, M=3, H=5이고, 각 공방이 가진 널빤지의 길이가 다음의 표와 같다고 해보자.

공방 번호	1번	2번	3번
가진 널빤지의 길이	2, 1	1	3, 2

전체 길이가 정확히 5가 되는 방법을 모두 적으면 다음의 표와 같다.

방법	1번 공방	2번 공방	3번 공방	전체 길이
1	길이 2	받지 않음	길이 3	5
2	길이 2	길이 1	길이 2	5
3	길이 1	길이 1	길이 3	5

따라서 현재 예시에서의 정답은 3이다.

길이가 같은 널빤지를 따로 센다는 점을 짚어 두자. N=2, M=2, H=3이고 1번 공방이 길이 1인 널빤지 두 장을, 2번 공방이 길이 2인 널빤지 한 장을 가지고 있다고 해보자.

공방 번호	1번	2번
가진 널빤지의 길이	1, 1	2

1번 공방에서 받을 수 있는 널빤지가 두 장이고 둘의 길이가 모두 1이지만, 어느 장을 받았는지가 다르므로 방법은 2가지다. 이어 붙인 울타리의 모양은 둘 다 길이 1과 길이 2가 나란히 놓인 모양으로 같지만, 받은 널빤지가 다르므로 따로 센다.

공방을 모두 지나도 전체 길이가 H가 되지 않는 경우도 있다. 가진 널빤지가 모두 짧아서 전부 받아도 H에 못 미치는 경우가 그렇다. 이때는 방법이 하나도 없으므로 0을 출력한다.

입력

출력

입력

2 2 3
1 1
2

출력

입력

출력

가장 먼저 첫째 줄에 공방의 수 N과 한 공방이 가질 수 있는 널빤지의 최대 장수 M, 그리고 만들려는 울타리의 길이 H가 공백으로 구분되어 주어진다. N과 M과 H는 모두 1 이상 50 이하의 자연수다.
이어서 N개의 줄에 걸쳐 1번 공방부터 N번 공방까지 각 공방이 가진 널빤지의 길이가 차례대로 주어진다. 한 줄에는 그 공방이 가진 널빤지의 길이가 공백으로 구분되어 주어지며, 널빤지의 장수는 1 이상 M 이하다. 각 널빤지의 길이는 1 이상 50 이하의 자연수다.

울타리의 전체 길이가 정확히 H가 되도록 널빤지를 받는 방법의 수를 10,007로 나눈 나머지를 한 줄에 출력한다. 길이가 정확히 H인 울타리를 만들 수 없으면 0을 출력한다.

한 공방에서 받는 널빤지는 최대 한 장입니다
널빤지를 받지 않고 지나가는 공방이 있어도 됩니다
길이가 같은 널빤지도 서로 다른 널빤지로 세어 구분합니다
전체 길이가 H보다 짧거나 길면 세지 않습니다
답은 10,007로 나눈 나머지로 출력합니다
표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
쓸 수 있는 말은 파이썬, 자바스크립트입니다
메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
케이스 15개를 전부 통과해야 해결입니다.

문제의 요구 사항을 잘 읽고 해결해 주세요. 단, 채점 과정을 건드려 통과한 것처럼 꾸미는 경우 적발 시 제재될 수 있습니다. 제출한 코드는 순위표에 함께 공개됩니다.

공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.

입력

기대 출력

2 2 3
1 1
2

코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.

0자1줄메모리 256MB (적어만 둡니다)기준 9.0ms

제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.

공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.

아직 없습니다. 첫 번째가 되실 수 있습니다.