FFT 알고리즘 질문입니다

알고리즘 문제 풀어보고 있던 중인데 도저히 어떻게 접근해야하는지 모르겠어서 글 남겨봅니다

가방안에 N개의 동전이 있을 때, 각각의 동전들은 1부터 M까지의 가치를 가지고 있습니다 (M >= N). 몇몇 동전들은 서로 같은 가치를 가지고 있을 수 있습니다. 이 가방에서 2개의 동전을 꺼낸 후 2개의 동전의 합을 기록합니다. 동전들로 만들 수 있는 가능한 합을 구할 수 있는 O(M log M) 알고리즘을 O(M log M) 설명하세요.

예> 만약 N=3 이고 가방안에 1, 4, 5 의 동전이 있을 때 가능한 합은 5, 6, 9 입니다

FFT 를 이용해서 polynomial을 구하면 될 것 같은데 잘 모르겠네요...

1답변

  • MlogM 알고리즘은 잘 모르겠는데요, 제가 생각한 알고리즘은 이렇습니다.

    더 좋은 방법이 있겠죠..

    #include <cstdio>
    
    int main(void)
    {
        int N, M;
    
        scanf("%d %d", &N, &M);
    
        int coin[N] = {0};
        int used[M + 1] = {0}; // 이미 쓴 적 있는 동전값 체크
        int gotsum[M*2 + 1] = {0}; // 이미 구한 적 있는 합체크 ....
    // M값의 동전 2개를 고를수 있으므로 M*2 + 1
    
        for(int i = 0 ; i < N ; i++)
            scanf("%d", &coin[i]);
    
        for(int i = 0 ; i < N-1 ; i++)
        {
            int first_coin = coin[i];
    
            if(used[first_coin] == 1)
                continue;
    
            used[first_coin] = 1;
    
            for(int j = i + 1 ; j < N ; j++)
            {
                int second_coin = coin[j];
                int sum = first_coin + second_coin;
    
                if(gotsum[sum] == 1)
                    continue;
    
                gotsum[sum] = 1;
                printf("합 : %d\n", sum);
            }
        }
        return 0;
    }
    
    

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

작성한 답변에 다른 개발자들이 댓글을 작성하거나 댓글에 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.