글 읽기 - 우째서 틀렸을까요

playsworld16 3년 전 0

*제 논리가 설명되어있으니 혼자 풀고싶으시다면 뒤로가기 누르세요.

n개의 input을 a b 라고 표현하면

a <= b 인 경우는 무시해도 좋습니다. 0 에서 n으로 갈 테니 언젠간 목적지에 분명히 다다를 것이기 때문입니다.

그래서 a > b인 경우들만 벡터에 {b, a} pair로 저장하고

정렬한 다음에 sweeping으로 겹치는 부분을 제외한 총 길이를 구해서

그 값의 두배만큼 m에 더한 값을 출력하게끔 했습니다.

integer 범위를 넘을 수도 있어서 long long으로 바꿨지만 그래도 틀렸습니다.

무엇이 문제일까요?

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    
    ll n, m, a, b;
    cin >> n >> m;
    
    vector<pair<ll ,ll>> A;
    for (int i = 0; i < n; i++){
        cin >> a >> b;
        if (a > b) A.push_back({b, a});
    }
    sort(A.begin(), A.end());
    
    ll ans = 0;
    ll l = 0, r = 0;
    for (auto i : A){
        tie(a, b) = i;
        if (a <= r) r = b;
        else {
            ans += r-l;
            l = a;
            r = b;
        }
    }
    
    ans += r - l;
    
    cout << m + 2*ans;
}

pl0892029 3년 전 2

if (a <= r) r = b;

r은 sweeping 시 커버하는 최대 좌표가 나와야되는데, 위에서는 단순 대입만 하고 있네요.

r = max(r, b);

를 의도하신 것 아닌가요?

playsworld16 3년 전 0

아.. 맞습니다...

아까 전에 다른 스위핑 문제 풀 때도 같은 실수를 했었는데...

다음부턴 그걸 최우선으로 생각해봐야겠네요 ㅜㅜ

감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

우째서 틀렸을까요

playsworld16 3년 전 0

pl0892029 3년 전 2

playsworld16 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말