광고 블록
문제
한 방송국이 내보낼 광고 영상 N개를 내보낼 순서대로 늘어놓았다. 1번부터 N번까지의 각 광고에는 그 광고의 길이가 초 단위의 자연수로 적혀 있다.
편성 담당자는 늘어놓은 순서에서 연달아 이어진 광고 몇 개를 묶어 하나의 광고 블록으로 쓰려고 한다. 다만 방송국의 편성 규칙상, 묶은 광고들의 길이 합이 M의 배수일 때만 광고 블록으로 쓸 수 있다. 광고 하나만으로 블록을 만드는 것도 허용한다. 또한 시작한 광고나 끝난 광고가 다르면 서로 다른 블록으로 센다.
광고의 길이 정보와 기준이 되는 수 M이 주어졌을 때, 광고 블록으로 쓸 수 있는 구간의 개수를 계산하는 프로그램을 작성하여라.
예를 들어 N=5개의 광고 길이가 다음의 표와 같고, M=3이라고 해보자.
| 번호 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 길이 | 1 | 2 | 3 | 1 | 2 |
길이 합이 3의 배수가 되는 구간을 모두 찾아 정리하면 다음의 표와 같다.
| 블록 | 1번 | 2번 | 3번 | 4번 | 5번 | 6번 | 7번 |
|---|---|---|---|---|---|---|---|
| 묶은 광고 | 1번부터 2번 | 1번부터 3번 | 1번부터 5번 | 2번부터 4번 | 3번 하나 | 3번부터 5번 | 4번부터 5번 |
| 길이 합 | 3 | 6 | 9 | 6 | 3 | 6 | 3 |
N이 최대 100만이므로 모든 구간의 합을 하나씩 더해 보는 방법은 쓸 수 없다. 1번 광고부터 각 광고까지의 길이 합을 M으로 나눈 나머지를 적어 두면, 나머지가 같은 두 자리 사이에 놓인 구간의 합이 바로 M의 배수가 된다. 위 예시에서 나머지를 표로 정리하면 다음과 같다.
| 끝 광고 | 없음 | 1번 | 2번 | 3번 | 4번 | 5번 |
|---|---|---|---|---|---|---|
| 1번부터 더한 값 | 0 | 1 | 3 | 6 | 7 | 9 |
| 3으로 나눈 나머지 | 0 | 1 | 0 | 0 | 1 | 0 |
나머지가 0인 자리가 네 군데, 나머지가 1인 자리가 두 군데다. 같은 나머지를 가진 자리 가운데 둘을 고르는 경우의 수를 모두 더하면 6 + 1 = 7이다. 따라서 이 경우의 정답은 7이다.
입출력 예시
예시 1
입력
5 3 1 2 3 1 2
출력
7
예시 2
입력
2 2 44494498 236225094
출력
3
예시 3
입력
5 2 865967068 74128013 807610317 131868032 375553997
출력
7
입력 조건
가장 먼저 첫째 줄에 광고의 수 N과 기준이 되는 수 M이 공백으로 구분되어 주어진다. N은 1 이상 1,000,000 이하의 자연수다. M은 1 이상 1,000 이하의 자연수다.
이어서 둘째 줄에 1번부터 N번까지의 광고 길이가 공백으로 구분되어 한 줄에 주어진다. 각 광고의 길이는 1 이상 1,000,000,000 이하의 자연수다.
입력 전체의 크기는 최대 약 3.9MB다. 한 줄에 수가 최대 100만 개 들어오므로, 입력을 줄 단위로 읽어서 공백으로 나누는 방식으로 처리해야 한다.
출력 조건
광고 블록으로 쓸 수 있는 구간의 개수를 첫째 줄에 출력한다. 정답은 최대 500,000,500,000까지 커질 수 있다. 32비트 정수로는 담을 수 없는 크기이므로 자료형에 유의하여라.
요구사항
- 구간은 늘어놓은 순서에서 끊기지 않고 이어진 구간만 셉니다
- 광고 하나만으로 이루어진 구간도 구간으로 셉니다
- 시작한 광고나 끝난 광고가 다르면 서로 다른 구간으로 셉니다
- M이 1이면 모든 구간이 광고 블록이 됩니다
- 정답은 32비트 정수 범위를 넘을 수 있습니다
- N이 최대 100만이므로 모든 구간의 합을 하나씩 구하면 시간이 모자랍니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 512MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
2 2 44494498 236225094
3
5 2 865967068 74128013 807610317 131868032 375553997
7
5 3 1 2 3 1 2
7
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.