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을 구하면 될 것 같은데 잘 모르겠네요...


조회수 69


Hashcode banner summercoding

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;
}

  • 2018년 04월 12일에 작성됨

로그인이 필요한 기능입니다.

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 작성한 답변에 다른 개발자들이 댓글을 작성하거나 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.
► 로그인
► 계정만들기
Close