글 읽기 - 중복되는 무게가 있을 때의 배재 방법

115dkk 6년 전 0

다음과 같은 코드를 짜서 조금씩 바꿔 시도해봤으나 계속 틀립니다.

중복되는 무게가 있을 때의 올바른 해결책은 무엇인가요?

#include <cstdio>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
typedef struct{
    int no,color,big,sum=0;
} Ball;
 
Ball t[200000];
 
int tot, s[200000], tmp_sum;
 
void input();
void solve();
void output();
bool cmp1(Ball,Ball);
bool cmp2(Ball,Ball);
 
using namespace std;
 
int main()
{
    input();
    solve();
    output();
    return 0;
}
 
void input()
{
    scanf("%d",&tot);
    for(int i=0;i<tot;i++)
    {
        scanf("%d%d",&t[i].color,&t[i].big);
        t[i].no=i;
    }
}
 
void solve()
{
     
    sort(t,t+tot,cmp1);
     
    s[t[0].color] += t[0].big;
    tmp_sum += t[0].big;
     
    for(int i=1;i<tot;i++)
    {
        s[t[i].color]+=t[i].big;
        tmp_sum+=t[i].big;
        if(t[i].big==t[i-1].big)
        {
            t[i].sum=t[i].big+t[i-1].sum+s[t[i-1].color]-s[t[i].color];
        }
        else t[i].sum=tmp_sum-s[t[i].color];
    }
     
    sort(t,t+tot,cmp2);
}
 
void output()
{
    for (int i=0;i<tot;i++) printf("%d\n",t[i].sum);
}
 
bool cmp1(Ball a,Ball b)
{
    return a.big<b.big;
}
 
bool cmp2(Ball a,Ball b)
{
    return a.no<b.no;
}

zlzmsrhak 6년 전 0

이 문제의 경우 답을 구하는 단계(52~57번째 줄)과 공을 추가하는 단계(51번째 줄)로 나누어져 있습니다.

무게가 같은 공들에 대해서, 각각의 답을 구한 후, 한꺼번에 추가하는 방식으로 진행해야 합니다.

아마 아래 코드처럼 진행될 것 같습니다.

추가로, s 배열 크기가 1 작습니다.

for(int i=0, j=0;i<tot;i=j)
{
    int j;
    for(j = i; j < tot && t[i].big == t[j].big; j++);
    for(int k = i; k < j; k++) t[k].sum = tmp_sum - s[t[k].color];
    for(int k = i; k < j; k++) s[t[k].color]+=t[k].big;
    for(int k = i; k < j; k++) tmp_sum+=t[i].big;
}

115dkk 6년 전 0

그렇게 접근하면 O(N²)이 되어 시간초과납니다. (입력 개수 최대 20만*탐색 횟수 최대 10만=200억=시간 초과)

다른 방법이 없을까요...

zlzmsrhak 6년 전 0

?!? 저 코드는 O(N)인데요..

115dkk 6년 전 0

저는 소스 코드를 다음과 같이 수정해서 사용하였습니다. (참고로 저는 1~2번에서 [0]을 미리 더한채 시작했기 때문에 i는 1부터 시작하고, 님과 같은 순서대로 for문을 진행하면 오답이 되므로 8~10번을 뒤집어놨습니다. int j는 중복선언이기 때문에 그대로 때려박을 경우 컴파일 에러가 일어나 삭제했습니다.)

그런데 이 방법으로 해결을 시도하면 시간 초과가 발생합니다. O(N)일 경우, 최대 20만의 탐색횟수이므로 시간 초과가 날 수 없는 문제입니다.

이는 이 알고리즘이 O(N)을 초과하는 복잡도를 요구하거나, 어딘가 시간을 잡아먹는 부분이 있다는 의미입니다. O(N²)이라는 것은 제가 섣불리 판단한 것 같습니다. 죄송합니다.

참고로 저는 iostream (cin/cout) 안씁니다. 즉, 입출력 때문에 동작 속도가 지연된 것은 아닙니다.

    s[t[0].color] += t[0].big;
    tmp_sum += t[0].big;  

    for(int i=1,j=0;i<tot;i=j)
        {
            for(j = i; j < tot && t[i].big == t[j].big; j++);
            j--;
            for(int k = i; k < j; k++) tmp_sum+=t[i].big;
            for(int k = i; k < j; k++) s[t[k].color]+=t[k].big;
            for(int k = i; k < j; k++) t[k].sum = tmp_sum - s[t[k].color];
        }

115dkk 6년 전 0

아, 댓글 내용이 수정되지 않는군요.

for문 진행을 님 식으로 뒤집어 놨는데, 틀렸다고 나오진 않고 시간초과만 튀어나옵니다.

그리고 생각해보니 님 식이 맞는 것 같습니다.(같은 무게일 경우 일단 더하지 말고 결과부터 계산하는게 맞을 테니까요.)

하지만 시간 초과는 왜 생기는지 모르겠습니다...

참고로 j-- 코드를 뺄 경우 오답이 발생합니다. 어떤 이유인지는 기억나지 않지만...

zlzmsrhak 6년 전 0

너무 오래 되서 기억은 잘 나지 않지만 수정한 부분이 꽤 되었던 것 같습니다.

확인해보세요

#include <cstdio>
#include <iostream>
#include <algorithm>
  
using namespace std;
  
typedef struct{
    int no,color,big,sum=0;
} Ball;
  
Ball t[200000];
  
int tot, s[200002], tmp_sum;
  
void input();
void solve();
void output();
bool cmp1(Ball,Ball);
bool cmp2(Ball,Ball);
  
using namespace std;
  
int main()
{
    input();
    solve();
    output();
    return 0;
}
  
void input()
{
    scanf("%d",&tot);
    for(int i=0;i<tot;i++)
    {
        scanf("%d%d",&t[i].color,&t[i].big);
        t[i].no=i;
    }
}
  
void solve()
{
      
    sort(t,t+tot,cmp1);
      
    for(int i=0, j=0;i<tot;i=j)
    {
        for(j = i; j < tot && t[i].big == t[j].big; j++);
        for(int k = i; k < j; k++) t[k].sum = tmp_sum - s[t[k].color];
        for(int k = i; k < j; k++) s[t[k].color]+=t[k].big;
        for(int k = i; k < j; k++) tmp_sum+=t[k].big;
    }
      
    sort(t,t+tot,cmp2);
}
  
void output()
{
    for (int i=0;i<tot;i++) printf("%d\n",t[i].sum);
}
  
bool cmp1(Ball a,Ball b)
{
    return a.big<b.big;
}
  
bool cmp2(Ball a,Ball b)
{
    return a.no<b.no;
}

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

문제

문제

출처

ICPC

중복되는 무게가 있을 때의 배재 방법

115dkk 6년 전 0

zlzmsrhak 6년 전 0

115dkk 6년 전 0

zlzmsrhak 6년 전 0

115dkk 6년 전 0

115dkk 6년 전 0

zlzmsrhak 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말