백준 17041 Measuring Traffic (USACO February 2019 Bronze 3번)

문제 링크: https://www.acmicpc.net/problem/17041

17041번: Measuring Traffic

1. N마일 지나고 나서 range를 구하는것과 2. 1마일 이전에 range를 구하는것 두가지 경우로 나눠서 풀이함.

1. 가장 왼쪽에 있는 none 구간을 시작으로 오른쪽으로 훑으면서 on을 만날때, off를 만날때, none을 만날때 각각의 케이스마다 적절한 계산을 하면서 답을 업데이트 시킴.

2. 가장 오른쪽에 있는 none 구간을 시작으로 왼쪽으로 훑으면서 위와 똑같이 실행함.

* 이문제는 AC를 받지 못해서 test data를 참고했음. 답을 업데이트 시키는 과정에서 음수가 나오는 경우가 있는데, 예외처리를 해줘야함. 아래 코드는 그 예외처리를 안해줘서 AC를 못받은 코드임.

#include <bits/stdc++.h>
using namespace std;
 
int n, a[101], b[101];
string ramp[101];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    int left = -1, right = -1;
    for(int i = 0; i < n; i++) {
        cin >> ramp[i] >> a[i] >> b[i];
        if(ramp[i] == "none" && left == -1) left = i;
        if(ramp[i] == "none") right = i;
    }
 
    int ans3 = -1e9, ans4 = 1e9;
    for(int i = left; i < n; i++) {
        if(ramp[i] == "none") {
            ans3 = max(ans3, a[i]);
            ans4 = min(ans4, b[i]);
        }
        if(ramp[i] == "on") {
            ans3 += a[i];
            ans4 += b[i];
        }
        if(ramp[i] == "off") {
            ans3 -= b[i];
            ans4 -= a[i];
        }
    }
 
    int ans1 = -1e9, ans2 = 1e9;
    for(int i = right; i >= 0; i--) {
        if(ramp[i] == "none") {
            ans1 = max(ans1, a[i]);
            ans2 = min(ans2, b[i]);
        }
        if(ramp[i] == "on") {
            ans1 -= b[i];
            ans2 -= a[i];
        }
        if(ramp[i] == "off") {
            ans1 += a[i];
            ans2 += b[i];
        }
    }
 
    cout << ans1 << ' ' << ans2 << '\n';
    cout << ans3 << ' ' << ans4 << '\n';
    return 0;
}
 

아래코드가 예외처리를 해준 후 AC를 받은 코드임.

#include <bits/stdc++.h>
using namespace std;
 
int n, a[101], b[101];
string ramp[101];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    int left = -1, right = -1;
    for(int i = 0; i < n; i++) {
        cin >> ramp[i] >> a[i] >> b[i];
        if(ramp[i] == "none") {
            if(left == -1) left = i;
            right = i;
        }
    }
 
    int ans3 = -1e9, ans4 = 1e9;
    for(int i = left; i < n; i++) {
        if(ramp[i] == "on") {
            ans3 += a[i];
            ans4 += b[i];
        }
        else if(ramp[i] == "off") {
            ans3 = max(0, ans3 - b[i]);
            ans4 = max(0, ans4 - a[i]);
        }
        else {
            ans3 = max(ans3, a[i]);
            ans4 = min(ans4, b[i]);
        }
    }
    int ans1 = -1e9, ans2 = 1e9;
    for(int i = right; i >= 0; i--) {
        if(ramp[i] == "on") {
            ans1 = max(0, ans1 - b[i]);
            ans2 = max(0, ans2 - a[i]);
        }
        else if(ramp[i] == "off") {
            ans1 += a[i];
            ans2 += b[i];
        }
        else {
            ans1 = max(ans1, a[i]);
            ans2 = min(ans2, b[i]);
        }
    }
 
    cout << ans1 << ' ' << ans2 << '\n';
    cout << ans3 << ' ' << ans4 << '\n';
    return 0;
}