글 읽기 - vector<T>(1000)은 틀리고 array<T,1000>은 맞음

tori1753 2년 전 0

array<pair<int,int>,1005> arr로 하면 맞았습니다!가 잘 나옵니다.

vector<pair<int,int>> arr(1005)로 하면 1%~3%에서 틀렸습니다가 나옵니다.

혹시몰라 array와 vector모두 {0,0}으로 초기화 후에 진행해도 같은 결과가 나왔습니다.

이럴수가 있나요?

//baekjoon ps 13904

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, sum = 0;
    cin >> n;
    //array<pair<int, int>, 1005> arr; 맞음
    //vector<pair<int,int>> arr(1005); 틀림
    for (int i = 1; i <= n; ++i)
        cin >> arr[i].second >> arr[i].first;
    sort(arr.begin() + 1, arr.end(), greater<pair<int, int>>());
    array<bool, 1000 + 1> check;
    for (int i = 1; i <= n; ++i)
    {
        auto [score, day] = arr[i];
        for (int idx = day; idx >= 1; --idx)
            if (!check[idx])
            {
                sum += score;
                check[idx] = true;
                break;
            }
    }
    cout << sum;
    return 0;
}

tori1753 2년 전 0

제 생각에는 데이터가 다 양수고 begin()+1부터 end()까지 greater로 정렬후 [1,n]사이 데이터만 사용하기 때문에 이상하게 정렬될거같진 않습니다. 설사 이상하게 정렬된다고 쳐도 같은 문제가 array에도 발생되어야 하지 않을까요?

tongnamuu 2년 전 1

array bool 의 check를 false로 초기화하고 해보시겠어요?

tongnamuu 2년 전 1

bool을 초기화하니 맞았다고 나오네요

//baekjoon ps 13904

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, sum = 0;
    cin >> n;
    //array<pair<int, int>, 1005> arr; 맞음
    vector<pair<int,int>> arr(1005);
    array<bool, 1000 + 1> check;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i].second >> arr[i].first;
        check[i] =false;
    }
    sort(arr.begin() + 1, arr.end(), greater<pair<int, int>>());

    for (int i = 1; i <= n; ++i)
    {
        auto [score, day] = arr[i];
        for (int idx = day; idx >= 1; --idx)
            if (!check[idx])
            {
                sum += score;
                check[idx] = true;
                break;
            }
    }
    cout << sum;
    return 0;
}

tori1753 2년 전 0

해결됨을 확인하였습니다! bool array를 초기화할 생각을 못했네요.. 하지만 아직 의문인게 똑같이 bool array는 초기화가 안되어있는데 array와 vector의 결과가 다른이유 혹시 알고계시나요..

tongnamuu 2년 전 1

그냥 우연히 초기화가 0으로 된 것 같네요
array<bool > 사이즈바꾸면서 돌려보니 0으로 초기화안되는 경우도있더라구요

tori1753 2년 전 0

감사합니다!

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

문제

문제

출처

ICPC

vector<T>(1000)은 틀리고 array<T,1000>은 맞음

tori1753 2년 전 0

tori1753 2년 전 0

tongnamuu 2년 전 1

tongnamuu 2년 전 1

tori1753 2년 전 0

tongnamuu 2년 전 1

tori1753 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말