Per ardua ad astra.

문제 수 N개 $A_1, A_2, ..., A_N$ 이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, $A_i + … + A_j$ (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력 첫째 줄에 N과 M이 주어진다. ($1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3$) 둘째 줄에 N개의 수 $A_1, A_2, ..., A_N$ 이 주어진다. ($0 ≤ A_i ≤ 10^9$) 출력 첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 예제 입력 1 5 3 1 2 3 1 2 예제 출력 1 7 알고리즘 분류 수학 누적 합 문제 출처 https://www.acmicpc.ne..

스타트와 링크 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 $S_{ij}$는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. $S_{ij}$는 $S_{ji}$와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 $S_{ij}$와 $S_{ji}$이다. N=..

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 $A_1 ≤ A_2 ≤ ... ≤ A_{K-1} ≤ A_{K}$ 를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 예제 입력 1 3 1 예제 출력 1 1 2 3 예제 입력 2 4 2 예제 출력 2..

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 예제 입력 1 3 1 예제 출력 1 1 2 3 예제 입력 2 4 2 예제 출력 2 1 2 1 3 1 4 2 3 2 4 3 4 예제 입력 3 4 4 예제 출력 3 1 2 3 4 알고리즘 분류 백트래킹 문제 출처 https://www...

문제 ${n \choose m}$의 끝자리 $0$의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 $n$, $m$ ($0≤m≤n≤2,000,000,000$ $n \ne 0$)이 들어온다. 출력 첫째 줄에 $n \choose m$의 끝자리 $0$의 개수를 출력한다. 예제 입력 1 25 12 예제 출력 1 2 알고리즘 분류 수학 정수론 문제 출처 https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 문제 해결 방법 '팩토리얼 0의 개수' 문제와 비슷한 유형의 문제이다. 팩토리얼에서 0의 개수는 5의..

문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지..

경우의 수 어떤 상황에 부딪혔을 때, 그 상황에서 나타날 수 있는 모든 경우의 수를 생각해야 할 때가 빈번히 발생한다. 합의 법칙과 곱의 법칙 합의 법칙(Rule of Addition) 서로 소인 두 집합 `A` 와 `B` 의 원소의 수를 각각 `n(A)`, `n(B)` 라고 하면, 두 집합이 서로 소이므로 합집합 `A ∪ B` 의 원소의 개수는 `n(A ∪ B) = n(A) + n(B)` 이다. 이와 같이 동시에 발생하지 않는 두 사건 `A` 와 `B` 가 일어나는 경우의 수를 각각 `m` 과 `n` 이라 할 때, 사건 `A` 또는 사건 `B` 가 일어나는 경우의 수는 `m + n` 이고, 이를 합의 법칙 (Rule of Addition)이라 한다. 예제 1 : 책상 위에 서로 다른 연필 5자루와 서로..