https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 풀이 최대 시간복잡도가 질문 수 200,000 * 문제 수 200,000 이기 때문에 100점을 맞기 위해서는 완전탐색으로는 무리가 있다. 탐색 했던 곳을 재탐색할 필요가 없기 때문에 누적합을 이용했다. 한번의 탐색으로 각 구간별 알파벳의 갯수를 누적합으로 저장했다. 그리고 L ~ R 구간을 구할 때 누적합으로 저장된 R - 1 번째 항에서 L 번..

https://www.acmicpc.net/problem/12841 12841번: 정보대 등산 숭실 대학교 정보 과학관은 숭실 대학교 건물 중 제일 높은 곳에 있다. 민주는 평소에 버스를 타고 이 언덕을 오르지만, 이 문제에 등장하기 위하여 오늘 하루만 걸어서 올라간다. 정보 과학관을 www.acmicpc.net 풀이 기본적인 누적합 문제이다. 사실 바로 누적합 문제인지 알진 못했고 완전 탐색을 진행했을 때 시간복잡도가 10만 * 10만, 시간초과가 나올 듯 하여 경우의 수를 줄이는 방법을 생각하다보니 알게 되었다. 우선, 그림을 그려보니 위와 같은 식으로 테이블을 짤 수 있었다. 빨간색이 지나는 부분을 다 더해주면 답을 구할 수 있다. 하지만 이 방법으로 하면 시간초과가 발생한다. 처음 횡단보도를 건넌..