- 문제 링크
백준 11659번 - 구간 합 구하기4
해결 전략
본인의 PS 실력이 여전히 많이 부족함을 느낀다. CS 이론이나, 시간을 오래 투자해야하는 깊이 있는 학부 프로젝트에는 참 잘한다고 느끼는데, PS에 있어서는 늘 자신감이 떨어진다. 극복하자. 이런 간단한 문제는 말그대로 간단히 풀어야할 것 아닌가.
이런 얘기를 하는 이유는, 본 문제를 풀 때, '매우 간단한 접근법'을 발견하지 못하고 거의 1시간 가량을 'Binary Search 기반 접근법'에 매몰되어 시도했다는 점이 참 스스로 실망스러워서이다.
물론, Binary Search 방식 접근이 좋지 않았던 것은 아니다. 다만, 본 문제의 입력 범위 및 제한 조건을 고려했을 때 적절치 않았던 것이다. 본 문제는 사실 이분 탐색을 전혀 사용하지 않아도 된다. 문제의 조건과 입력 상황을 고려하면 다음과 같은 사실을 발견할 수 있기 때문이다.
애초에 입력받을 때 쭉 '누적합'을 계산해놓으면, 부분합 구하는건 식은 죽 먹기다(도 아니다).
~> 그렇다. 애초에 입력받을 때 문제를 풀어버리는 것이다. 왜 이 간단한 아이디어를 떠올리지 못했을까. 평소에는 이런 번뜩이는 접근법을 잘 떠올렸던 것 같은데, 오늘은 참 아쉽다. 후..
아래는 정답 코드이다.
#include <iostream>
// BOJ - 11659 Summing each range 4
using namespace std;
int psum[100001];
int main(void) {
int n, m, a, b, temp;
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> temp;
psum[i] = psum[i - 1] + temp;
}
for (int i = 0; i < m; i++) {
cin >> a >> b;
cout << (psum[b] - psum[a - 1]) << '\n';
}
return 0;
}