기로에 서다

문제 www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 풀이 1. 조는 친구들을 우선 체크한 후, 출석 번호를 받은 친구들의 배수마다 출석했다고 체크를 하는데 조는 친구들은 무시하고 넘어가면 됩니다. 2. 이 때 구간질의마다 학생 수를 세면 시간초과가 나기 때문에 미리 누적합 배열을 저장해놓고, [s, e] 구간의 합에 대해psum[e] - psum[s - 1]을 출력하면 해결할 수 있습니다. 코드 #include ..

문제 www.acmicpc.net/problem/3673 3673번: 나눌 수 있는 부분 수열 양의 정수로 이루어진 수열이 주어졌을 때, 연속하는 부분 수열의 합이 d로 나누어 떨어지는 것의 개수를 구하는 프로그램을 작성하시오. 예를 들어, 아래와 같은 수열의 부분 수열 중 4로 나누�� www.acmicpc.net 문제 풀이 1. n의 범위로 보아 연속된 부분수열의 합을 구하기 위해 누적합을 사용한다고 생각했습니다. 2. 시작점이 고정된 연속 부분수열의 합이 아니므로 구해야하는건 시작점을 s, 끝점을 e라 할 때, 구간[s,e]의 누적합이 (psum[e] - psum[s-1])%d ==0을 만족하는 (s,e)쌍을 찾는 것과 같았고, 이는 (psum[e] % d) == (psum[s - 1] % d)와 ..