저기.. 인형문제 질문좀 할게요..

  • 공상가
    공상가
    #include <iostream>
    #define MAX 100000
    using namespace std;
    typedef struct _array {
        int val;
        int idx;
    } array;
    array arr[MAX];
    array temp[MAX];
    int used[MAX]={0};
    void merge(int,int,int*);
    void program();
    int main() {
        int n;
        cin>>n;
        while(n--)
            program();
        return 0;
    }
    void merge(int left,int right) {
        if((right-left)<=1) return;
        int half=(left+right)/2;
        merge(left,half);
        merge(half,right);
        int i,j,k;
        i=left;
        j=half;
        k=left;
        while(i<half&&j<right) {
            if(arr[i].val>arr[j].val) {
                temp[k].val=arr[j].val;
                temp[k++].idx=arr[j++].idx;
            } else {
                temp[k].val=arr[i].val;
                temp[k++].idx=arr[i++].idx;
            }
        }
        while(i<half) {
            temp[k].val=arr[i].val;
            temp[k++].idx=arr[i++].idx;
        }
        while(j<right) {
            temp[k].val=arr[j].val;
            temp[k++].idx=arr[j++].idx;
        }
        for(i=left;i<right;i++) {
            arr[i].val=temp[i].val;
            arr[i].idx=temp[i].idx;
        }
    }
    void program() {
        int t_type, t_num; //전체 종류의 수, 기부되어야 할 인형
        int t_doll; // 인형의 전체 수
        int range; //아래에 설명됨
        int temp;
        int temp2;
        int i;
        int cond;
        cin>>t_type>>t_num;
        t_doll=0;
        for(i=0;i<t_type;i++) {
            cin>>arr[i].val;
            arr[i].idx=i;
            t_doll+=arr[i].val;
            used[i]=0;
        }
        merge(0,t_type);
        range=t_num-1;
        for(i=0;i<t_type;i++) {
            if(t_num>0) {
                cond=(arr[i].idx<=(range%t_type)); // 보정값 : 만약 현재 배열의 인덱스가 Range의 값의 영역에 포괄되는지..(설명하기가 좀 애매;;;)
                temp=(range/t_type)+cond; // 자주 사용되므로 Temp변수로 설정함.. 그 인덱스에 해당하는 인형이 몇개 필요한지, 혹은 몇개가 부족한지 알아보기 위해 만든 변수에요..
                if(arr[i].val<temp) { // 만약 작다면, 작은값인 인형이 현재의 인덱스에서 가지고 있는 인형의 수...를 제시하는게
                    temp2=temp-arr[i].val; // 그 차를 구하고
                    used[arr[i].idx]=arr[i].val;//그만큼 사용됐다고 통보하고
                    t_num-=arr[i].val; //요구된 인형의 수에서 차만큼 빼고
                    range+=temp2; // 차 만큼 Range범위를 늘리고
                    arr[i].val=0;// 초기화 시켜주고
                    continue; //다음으로 휘리릭..
                } else {
                    arr[i].val-=temp; // 같거나 혹은 크면.. 요구된 만큼 쑥 뺀다.
                    used[arr[i].idx]=temp;// 그만큼 지정하고
                    t_num-=temp;//전체 요구하는 인형의 수에서 남는 인형의 수..
                }
            } else {
                break;
            }
        }
        if(t_num>0) used[arr[i-1].idx]+=(t_num>arr[i-1].val?arr[i-1].val:t_num);
        for(i=0;i<t_type;i++) {
            cout<<used[i]<<" ";
        }
        cout<<endl;
    }
    

    인형 문제를 풀었는데, 이게 좀 많이 이상하네요... 분명히 문제에 주어진 "입력"값을 참조하여 값들을 넣어봤을 때는,
    정말이지 아무 문제 없이 잘 돌아갑니다.. 근데, 여기에 올리는 순간 에러가 발생해요...
    에러에서는 컴파일은 무난하게 넘어갑니다. 이제 정해진 값대로 출력되는지에 대한 판단에서 틀리는거죠..;;
    제가 사용한 알고리즘은 이러해요...
    사실 시뮬레이션을 직접 시켰던걸, 일종의 1차원적 접근으로 변형시킨것 뿐인데요...
    1 5 2 가 있다고 가정하면
    (각각 A,B,C라고 할 때..)
    A B C 0 B C 0 B 0 0 B 0 0 B 0
    이런식으로 주욱 늘여놓습니다.
    그리고 만약 5개를 뽑으라 한다면,
    A B C 0 B | C 0 B 0 0 B 0 0 B 0 (저기 파이프라인지점)
    이런식으로 설계가 되죠..
    안에 0이 하나 있으니까,
    A B C 0 B C | 0 B 0 0 B 0 0 B 0
    이렇게 Range를 늘려가면서 하는건데,
    여기서 일단 값들을 Merge소트를 통해서 정렬을 했고,
    실제로도 그 값들이 정렬되는 것도 확인했으며,(그랬으니까 문제에 있는 입력값들이 정확히 출력이 됐겠죠..ㅠ_ㅠ)
    여튼 그러합니다...;;
    근데 도대체 뭐가 문제인건지 -_- 사람을 답답하게 하는군요...;;
    혹시 운영자님.. 여기 이 사이트에서 채점할 때 제시하는 값과 어떻게 차이가 나는건지...;;;
    보여주실 수 있었음...;; 하는 작은 바램이 -_-.... 있네요...ㅋㅋㅋㅋㅋ

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    15년 전
2개의 댓글이 있습니다.
  • Toivoa
    Toivoa

    코드를 보기 편하도록 본문을 수정하였습니다. ^^;
    코드의 작성 의도를 설명하신것 같지만, 설명이랑 코드가 약간 매치되지 않네요. 머지 소트를 왜 하셨는지 설명을 더 해주셨으면 이해하기 쉬었을 것 같습니다.
    일단 머지소트를 하신 이유는 stable한 소트를 위해서인것 같은데, (STL의 stable_sort를 사용하시거나, 이 문제의 Editorial (http://algospot.com/zbxe/?mid=editorial&document_srl=50203 에서와 같이 index를 가지고 소트하셔도 됩니다.)
    님의 접근 방법(코드)의 반례를 찾아보면 A와 B 1개, C와 D 4개에서 8개를 나눠준다고 할 때 (A B C D 0 0 C D | 0 0 C D 0 0 C D) 이 될텐데, A에서 2개를 나눠주어야 하는데 1개를 나눠줄 수 없으니 1칸을 밉니다. (A B C D 0 0 C D 0 | 0 C D 0 0 C D). 여기에서 B를 보면 B에서 2개를 나눠주어야 하는데 1개를 나눠줄 수 없으니 1칸을 밉니다. 그러면 (A B C D 0 0 C D 0 0 | C D 0 0 C D) 이 됩니다. C에서 2개를 나눠주고, D에서 2개를 나눠주겠죠? 나눠준 개수가 6개이니 2개가 남았습니다.

        if(t_num>0) used[arr[i-1].idx]+=(t_num>arr[i-1].val?arr[i-1].val:t_num);
    

    에서 나머지 2개를 D에 몰아줘서 답이 1 1 2 4가 나옵니다. 하지만 정답은 1 1 3 3이 맞습니다.
    에디토리얼에서는 님이 쓰신 접근법을 사용하지 않고, 인형의 개수가 가장 적은 것부터 나눠줄 개수를 확정할 수 있으니 나눠주고난 나머지를 이용해서 계산합니다. 에디토리얼 (위 링크)을 참고해보세요.


    15년 전 link
  • JongMan
    JongMan

    위대한 Toivoa...
    그리고 "이 사이트에서 채점할 때 제시하는 값과 어떻게 차이가 나는건지...;;; 보여주실 수 있었음...;; 하는 작은 바램"

    이거 사실 큰 바램이에요 ㅠ.ㅠ 무지 어려운 일입니당 ㅋㅋㅋ


    15년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.