15922번 아우으 우아으이야!!

https://www.acmicpc.net/problem/15922

알고리즘 문제를 본격적으로 공부하기 시작한 단계에서 풀려고 했었던 문제로 기억한다.

당시에 너무 어려웠던 것 같아서 못 푼 기억이 있었는데

지금 다시 풀어보니 바로 풀었다.

나의 아이디어는

그 전 좌표를 [bx, by],

그 다음 좌표(이제 입력할 좌표)를 [x, y]라고 한다면

여기에서 중요한 것은 by이다.

by의 위치는 3가지의 경우가 있다.

1. by x y

2. x by y

3. x y by

위의 3가지 경우를 잘 따져보고 구현하면 된다.

또한, 중요한 것은 by는 max(by, y)로 갱신해야 한다.

by를 무조건 y로 변경하면 아래와 같은 테스트 케이스에서 15를 출력한다.

4
1 10
3 3
3 4
3 9

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
 
int main()
{
    cin.tie(0);
    scanf("%d", &n);
    int bx, by, x, y, ans = 0;
    scanf("%d %d", &bx, &by);
    ans = abs(bx - by);
 
    for (int i = 0; i < n - 1; i++) {
        scanf("%d %d", &x, &y);
        if (by <= x && x < y) {
            ans += abs(x - y);
        }
        else if (x < by && by <= y) {
            ans += abs(by - y);
        }
        else if (x < y && y < by) {
            // 이해를 돕기 위하여 코드를 작성
            // 무시
        }
 
        by = max(by, y);
    }
 
    printf("%d\n", ans);
 
    return 0;
}