취업 준비 및 일상

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 장애물이 있는 범위를 누적합을 통해 구하면 됩니다: 가령, H=7이고 석순의 길이가 3이라면, 1, 2, 3이 영향을 받으므로, '석순 배열'의 3번째 index에 1을 넣고, H에서부터 1까지 누적합을 구하면 높이가 3인 석순이 1, 2, 3에 영향을 끼친다는 것을 구현할 수 있습니다. 반대로, 종유석의 길이가 3이라면 이는 7, 6, 5에 영향을 미치기에, '종유석 배열'의 5(=H+1-종유..

https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 솔직히 누적합 유형 문제는 껌이라고 생각했는데, O(N^2) 브루트포스 풀이말고 생각이 전혀 안 나더라... 내가 껌이였고 풀이 1. 누적합(sum[i]: 0번째 index부터 i번째 index까지의 합)을 구한다. 2. value는 Integer, key는 long으로 하는 map을 선언한 후, (0, 1)을 넣어준다. 이는 0..