# [Silver II] Golden Section Search [문제 링크](https://www.acmicpc.net/problem/33957) ## 문제 설명 <p>먼 훗날, PPC는 1학기와 2학기에 한 번씩, 1년에 총 2번 열리게 되었다.</p> <p>PPC 출제진은 $N$개의 문제를 미리 준비해 두었다. 각 문제는 $1$번부터 $N$번까지의 번호로 구분된다. 각 문제의 난이도 하한과 상한은 이미 정해져 있지만, 정확한 난이도는 정해져 있지 않다. $i$번 문제의 난이도 하한은 $L_i$, 난이도 상한은 $R_i$이다.</p> <p>PPC 출제진은 미리 준비해 둔 $N$개의 문제를 정확히 두 부분으로 나눠 각 대회에 출제하려 한다. 전체 문제 중 앞쪽 일부를 1학기 대회에, 남은 뒷부분을 2학기 대회에 배정할 것이다. 이때 학생들이 어느 대회에 출전해야 하는지 고민하지 않도록 두 대회의 난이도를 같게 하려 한다. 대회의 난이도란 대회에 배정된 문제들의 난이도를 모두 더한 값이다.</p> <p>두 대회의 난이도를 같게 하기 위해 PPC 출제진은 문제를 <strong>황금 분할</strong>하기로 했다. 구체적으로 아래와 같이 문제를 나누는 방법을 황금 분할이라 한다.</p> <ul> <li>각 대회에 적어도 $1$문제 이상이 출제되어야 하며 각 대회에 쓰이는 문제들의 번호는 연속해야 한다. 즉, $1$ 이상 $N$ 미만의 정수 $x$에 대해 $1$번 문제부터 $x$번 문제까지는 1학기 대회에, $x+1$번 문제부터 $N$번 문제까지는 2학기 대회에 출제한다.</li> <li>두 대회의 난이도가 같도록 각 문제의 난이도를 정할 수 있어야 한다. 즉, $\sum_{1\le i\le x}D_i=\sum_{x<i\le N}D_i$을 만족하도록 $i$번 문제의 난이도 $D_i$를 정할 수 있어야 한다. 이때 $D_i$는 $L_i$ 이상 $R_i$ 이하의 정수여야 한다.</li> </ul> <p>두 황금 분할이 다름은 각 분할에서 1학기 대회에 사용되는 문제의 수가 서로 다름을 의미한다. 배정된 난이도가 달라도 $x$값이 같다면 같은 분할이다.</p> <p>예를 들어 $N=3$, $L=[1,1,1]$, $R=[2,2,2]$인 경우를 생각하자. $x=1$인 경우에는 난이도를 $[2,1,1]$로, $x=2$인 경우에는 난이도를 $[1,1,2]$로 정하면 황금 분할의 조건을 만족하므로 서로 다른 황금 분할은 $2$개이다.</p> <p>서로 다른 황금 분할의 개수를 구하여라.</p> ## 입력 <p>첫 번째 줄에 문제의 수 $N$이 주어진다. ($2 \leq N \leq 100\,000$)</p> <p>두 번째 줄부터 $N$개의 줄에 걸쳐, $i+1$번째 줄에 $i$번째 문제의 난이도 하한과 상한을 나타내는 두 정수 $L_i$, $R_i$가 공백으로 구분되어 주어진다. $(0 \le L_i \le R_i \le 1000)$</p> ## 출력 <p>서로 다른 황금 분할의 개수를 구하여라.</p> ## 풀이 L의 누적합, R의 누적합을 미리 구해, 각각의 i에 대해 1 ~ i번의 합의 범위, i+1 ~ N번의 합의 범위를 O(1)에 구해 두 선분이 교차하는지 판별하였습니다. ``` c++ #include<bits/stdc++.h> using namespace std; int preMin[100'001], preMax[100'001]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=1;i<=n;i++) { cin >> preMin[i] >> preMax[i]; preMin[i] += preMin[i-1]; preMax[i] += preMax[i-1]; } int cnt=0; for(int i=1;i<n;i++) { int leftL = preMin[i], leftR = preMax[i]; int rightL = preMin[n]-preMin[i], rightR = preMax[n]-preMax[i]; if(leftL<=rightR && rightR<=leftR || leftL<=rightL && rightL<=leftR || rightL<=leftL && leftL<=rightR || rightL<=leftR && leftR<=rightR) cnt++; } cout << cnt; } ```