시아98
174
2020-11-12 21:50:06 작성 2020-11-12 21:50:32 수정됨
7
617

백준 14267번 문제인데... 시간초과가 뜨네요


일단 문제는 https://www.acmicpc.net/problem/14267 입니다.

배열이 간단하고 편할거 같아서 배열로 작성했는데 제 생각에 O(n^2)가 나오는 것 같은데도 시간초과가 걸리네요...

c언어로 짜고있습니다. 혹시 시간을 줄일  수 있는 부분이 있을까요..? 아무리봐도 제 눈에는 안보이네요..

#include <stdio.h>
#include <stdlib.h>

int n, m;

int main() {
    int number;
    int score;
    
    scanf("%d %d", &n, &m);
    
    int per[n]; //직원들의 상사 번호수
    int res[n]; //최종 스코어
    for(int i=0; i<n; i++)
        res[i] =0;
    
    for(int i=0; i<n; i++)
    {
        scanf("%d ", &number); //상사 번호수를 입력받아 per배열에 넣어줍니다.
        if(number<-1 || number>n)
            exit(1);
        per[i] = number;
    }
    
    for(int i=0; i<m; i++)
    {
        scanf("%d %d", &number, &score); //칭찬할 직원과 점수를 받아서
        
        res[number-1] += score;
        for(int j=0; j<n; j++)
        {
            if(per[j]>=number) // 직원의 상사가 칭찬받았으면 점수를 더해줍니다.
                res[j]+=score;
        }
    }
    
    for(int i=0; i<n; i++)
        printf("%d ", res[i]);
    
    
    return 0;
}
0
  • 답변 7

  • noIdle
    59
    2020-11-12 22:25:47

    칭찬할 직원하구 점수받았을 때, 굳이 모든 직원을 돌릴필요가 없지않을까요

  • yeori
    3k
    2020-11-12 22:31:38

    걍 누적해서 쭉 더하면 될거같은데요 O(n)

  • 시아98
    174
    2020-11-12 22:35:50

    //noldle 먼저 의견감사합니다. 말씀해주신 의도가 j의 시작을 다시 지정해주시라는 것 같습니다. 그래서 다시 보니 j=number로 해도 무방할 듯 보여서 했는데도 시간이 줄진 않았나보네요..

  • 시아98
    174
    2020-11-12 22:36:28
    //yeori 의견 감사합니다. 혹시 누적해서 더한다는게 자세히 어떤 말씀이신가요?
  • yeori
    3k
    2020-11-13 00:23:24

    이 문제 완전 낚시네요 -_-;

    칭찬 갯수 m에서 한 직원이 직속 상관한테서 여러번 칭찬받을 수 있다는 언급을 왜 안해놨는지....?

    진짜 어이가 없네...ㅎㅎ 이게 숨길 내용인가...ㅎㅎ

    어떻게든 못맞추게 하겠다는 의지가 돋보이는 문제임


  • 엡실론
    2k
    2020-11-13 03:37:16
    그냥 tree 순회하면서 더하면 O(n)에 되겠네요.
  • 시아98
    174
    2020-11-13 11:08:47

    답변 감사합니다

  • 로그인을 하시면 답변을 등록할 수 있습니다.