2015번: 수들의 합 4 - 누적 합, 자료구조(map)
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 1. 누적 합을 구한다. 2. 누적 합 배열(psum[i])의 최대 index부터 0까지 거꾸로 탐색하여, 누적 합의 값이 몇 번 나왔는지 저장한 map(psumMap)에서 psum[i] + K가 나온 횟수의 총합을 구한다. 이분 탐색과 정렬로 생각하기 쉬웠다. 문제만 보고 map을 떠올리기 쉽지 않았다. #define _SILE..
알고리즘/baekjoon
2023. 3. 11. 00:02
