21757번: 나누기 $N$개의 정수 수열 $A_1, A_2, \dots , A_N$이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어 www.acmicpc.net 문제 $N$개의 정수 수열 $A_1, A_2, \dots , A_N$이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어떤 $i, j, k$ ($1 \le i < j < k < N$)에 대해서$[A_1, \dots, A_i], [A_{i+1}, \dots, A_j], [A_{j+1}, \dots, A_k], [A_{k+1}..
문제풀이/누적합
10713번: 기차 여행 JOI나라에는 N개의 도시가 있고, 각 도시에 1,2,...,N까지의 번호를 갖고 있다. 그리고, 철도가 N-1개 있고, 각 철도에 1,2,...N-1의 번호를 갖고 있다. 철도 i (1 ≦ i ≦ N − 1)는 도시 i과 도시 i+1을 양방 www.acmicpc.net 문제 JOI나라에는 N개의 도시가 있고, 각 도시에 1,2,...,N까지의 번호를 갖고 있다. 그리고, 철도가 N-1개 있고, 각 철도에 1,2,...N-1의 번호를 갖고 있다. 철도 i (1 ≦ i ≦ N − 1)는 도시 i과 도시 i+1을 양방향으로 연결시키는 철도를 의미한다. JOI나라의 철도를 타는 방법에는, 티켓을 구입해 승차하는 방법과 IC카드로 승차하는 방법 두 가지가 존재한다. 철도 i에 티켓을 구..
13422번: 도둑 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마 www.acmicpc.net 문제 다음 그림과 같이 N개의 집이 순서대로 이웃하여 세워진 마을이 있다. 위 그림은 N = 8인 경우 마을의 모습이다. 위 그림과 같이 각각의 집은 순서대로 서로 이웃해 있으며, 첫 번째 집과 마지막 집 또한 이웃해 있다. 예를들면 3이 적힌 집은 9, 4가 적힌 집과 이웃해 있으며, 5가 적힌 집은 6, 7이 적힌 집과 이웃해 있다. 이 마을 사람들은 각자 자신의 집에 돈을 보관한다. 위 그림에서 각 집에 적혀 있는 숫자는 집마다 보관 중인 돈의 금액을 나타낸다. 어..
16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 문제 승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다. '문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.' 승재를 도와 특정 문자열 $S$, 특정 알파벳 $\alpha$와 문자열의 구간 $[l,r]$이 주어지면..
20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 첫째 줄에 지동이의 방에 출입한 모기의 마릿수 N(1 ≤ N ≤ 1,000,000)가 주어진다. 다음 N개의 줄에 모기의 입장 시각 TE과 퇴장 시각 TX이 주어진다. (0 ≤ TE
