글 읽기 - 정답처리를 받았지만 반례가 있는것 같습니다...

show981111 4년 전 0

먼저 첫번째 성적에 대해서 정렬을 한 뒤에, 순차적으로 값을 하나씩 선택해 나가면서 최댓값을 갱신하도록 했을때는 시간초과가 떳었습니다(즉 v[0] 을 고랐을때의 값, v[1]을 골랐을때의 값, v[2]를 골랐을때의 값... 나아가면서 최댓값을 갱신).

그래서 가장작은 v[0]을 포함시키는 경우에 무조건 최댓값을 구해낼 것 같아서 그렇게 해보았더니 시간초과도 안뜨고 정답처리를 받았습니다.

그런데, 만약 아래와 같은 경우에 (1,2)를 고른다면, (1,2)와 (4,1) 을 골라서 답이 2가나오지만, 최댓값은 (2,4),(3,3),(4,1) 을 고른 3이 있습니다.

1
4
1 2
2 4
3 3
4 1

잘못된것 아닌가요?
아래는 정답처리를 받은 코드입니다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 100005
using namespace std;
vector<pair<int,int>> v;
int testcase,n;
int main()
{
    scanf("%d",&testcase);
    while(testcase--)
    {
        scanf("%d",&n);
        for(int i = 0; i < n; i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            v.push_back(make_pair(x,y));/
        }
        sort(v.begin(),v.end());
        int cnt = 0;
        int max = 0;
        int tempy = 0;
        
        for(int i = 0; i < v.size(); i++)
        {
            if(i > 0) break;//i 가 0 인 경우를 선택하면 최댓값을 산출한다?
            tempy = v[i].second;
            cnt = 1;
            for(int j = i + 1; j < v.size(); j++)
            {
                if(tempy > v[j].second)
                {
                    tempy = v[j].second;
                    cnt++;
                }
            }
            if(max < cnt) max = cnt;
        }
        printf("%d\n",max);
        v.clear();
    }
    return 0;
}

djm03178 4년 전 2

(2,4)와 (3,3)은 (1,2)에게 지기 때문에 뽑히지 않습니다. 뽑히는 사람들 사이에서만 겨루는 것이 아니라 지원한 사람 전체에 대해서 하는 거기 때문입니다.

show981111 4년 전 0

아.. 감사합니다!

rlarjs7879 2년 전 0

아 저도 이런 반례를 생각했는데 전체 지원자군요...ㄷ

어려우면서도 쉽고... 이해력이 좋아야 하네요.

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

문제

문제

출처

ICPC

정답처리를 받았지만 반례가 있는것 같습니다...

show981111 4년 전 0

djm03178 4년 전 2

show981111 4년 전 0

rlarjs7879 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말