각재 이어 붙이기
문제
한 목공방에 길이가 서로 다른 각재 N개가 쌓여 있다. 각재의 길이는 모두 자연수이며, 길이가 같은 각재는 하나도 없다.
목수는 이 각재 가운데 두 개를 골라 끝과 끝을 이어 붙여서, 길이가 정확히 X인 기둥을 하나 만들려고 한다. 이어 붙이는 과정에서 길이가 줄어들거나 늘어나지는 않는다. 그래서 고른 두 각재의 길이 합이 정확히 X가 되어야 한다.
각재에는 쌓여 있던 순서대로 1번부터 N번까지 번호가 붙어 있으며, 길이 순으로 정리되어 있지는 않다. 목수는 기둥을 몇 가지 방법으로 만들 수 있는지 미리 세어 보려고 한다.
각재의 길이 정보와 만들려는 기둥의 길이 X가 주어졌을 때, 길이 합이 정확히 X가 되도록 두 각재를 고르는 경우의 수를 계산하는 프로그램을 작성하여라. 두 각재를 고르는 순서는 구분하지 않는다.
예를 들어 N=9개의 각재의 길이가 다음의 표와 같고, X=13이라고 해보자.
| 번호 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 길이 | 5 | 12 | 7 | 10 | 9 | 1 | 2 | 3 | 11 |
길이 합이 13이 되는 두 각재의 조합을 모두 찾아 정리하면 다음의 표와 같다.
| 조합 | 1번 | 2번 | 3번 |
|---|---|---|---|
| 고른 각재의 번호 | 2번과 6번 | 4번과 8번 | 7번과 9번 |
| 두 각재의 길이 | 12와 1 | 10과 3 | 2와 11 |
| 길이 합 | 13 | 13 | 13 |
남은 각재도 하나씩 짚어 보자. 1번 각재는 길이가 5이므로 길이가 8인 각재와 짝을 지어야 하는데, 길이가 8인 각재는 없다. 3번 각재는 길이가 7이라서 길이가 6인 각재가 필요하고, 5번 각재는 길이가 9라서 길이가 4인 각재가 필요하다. 둘 다 없다. 따라서 이 경우의 정답은 3이다.
길이가 모두 다르므로 한 각재가 두 개의 조합에 쓰이는 일은 없다. 또한 같은 각재를 두 번 쓸 수도 없다.
입출력 예시
예시 1
입력
9 5 12 7 10 9 1 2 3 11 13
출력
3
예시 2
입력
3 759742 101870 196135 417007
출력
0
예시 3
입력
2 553357 164263 1782794
출력
0
입력 조건
가장 먼저 첫째 줄에 각재의 수 N이 주어진다. N은 1 이상 100,000 이하의 자연수다.
이어서 둘째 줄에 1번부터 N번까지의 각재의 길이가 공백으로 구분되어 한 줄에 주어진다. 각 길이는 1 이상 1,000,000 이하의 자연수이며, 서로 같은 길이는 없다.
이어서 셋째 줄에 만들려는 기둥의 길이 X가 주어진다. X는 1 이상 2,000,000 이하의 자연수다.
입력 전체의 크기는 최대 약 0.7MB다. 한 줄에 수가 최대 10만 개 들어오므로, 입력을 줄 단위로 읽어서 공백으로 나누는 방식으로 처리해야 한다.
출력 조건
길이 합이 정확히 X가 되도록 두 각재를 고르는 경우의 수를 첫째 줄에 출력한다. 그런 조합이 하나도 없으면 0을 출력한다.
요구사항
- 각재의 길이는 서로 모두 다릅니다
- 같은 각재를 두 번 고를 수는 없습니다
- 두 각재를 고르는 순서는 구분하지 않습니다. 2번과 6번을 고른 것과 6번과 2번을 고른 것은 같은 경우로 셉니다
- 각재의 길이는 입력에 주어진 순서대로이며, 정렬되어 있지 않습니다
- 두 각재의 길이 합이 X보다 크거나 작으면 세지 않습니다. 정확히 X여야 합니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
2 553357 164263 1782794
0
3 759742 101870 196135 417007
0
9 5 12 7 10 9 1 2 3 11 13
3
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.