Problem Solving/누적합

[백준] 16139 인간-컴퓨터 상호작용 (누적합)

- 문제 설명 - 문제 풀이 서브테스크가 있는 문제이다. 본래 문제에서는 문자열의 길이가 200,000자 이하, 질문의 수는 200,000개 이하를 조건으로 되어있는데 만약 문자열의 길이가 2,000개 이하, 질문의 수가 2,000개 이하에서만 만족하는 시간복잡도를 갖는다면 50점만 맞는다. 때문에 시간복잡도를 잘 고려해야 하는 문제이고 주의할 점은 O(n^2)을 넘지 않는 것이다. 문자열의 문자가 알파벳 소문자만 있다는 것을 이용해서 범위가 2차원이지만 arr[26][문자열의 길이]를 사용한다. 문자열의 길이만큼인 이유는 최악의 경우 문자열이 모두 같은 알파벳일 수도 있기 때문이다. 반복문을 통해 순차적으로 문자열의 문자들을 검색하고 아스키 코드 값을 이용해 arr[문자 - 97] 인 곳들을 누적합을 ..