[백준]배열과 연산(14222)

문제 링크 : [백준]배열과 연산(14222)

문제 설명

N개의 값이 주어지고, 숫자 K가 주어집니다.
N개의 각각의 값에 K * x(x는 0도 가능, 즉 그 수를 유지해도 됩니다.)를 더하여, 1 ~ N 사이의 모든 수를 포함하는 수열을 만들 수 있는지 판별하세요.

입력

N(수의 갯수, 1 <= N <= 50)
K(더할 수, 1 <= K <= 10)
V_i(주어진 수, 1 <= V_i <= N)

8 1
1 1 1 1 1 1 1 1

출력

1

카테고리

#이분매칭

시간 복잡도 상한

매우 커도 될 것 같습니다.

해결 방법

1. 각 수들을 K * x를 더하여 만들 수 있는 수와의 관계를 그래프로 표현할 수 있습니다.
2. 실제로 상태(Ex. 숫자)간의 변경을 그래프로 표현하여 문제를 푸는 경우도 종종 있으니 익숙해질 필요가 있을 것 같습니다.
3. 그랬을 때, 모든 숫자로 표현을 할 수 있다는 것은, 주어진 수(그룹A)를 목적지(그룹B)의 숫자로 최대한 많이 매핑시켰을 때, 모든 숫자로 매핑이 되는지를 판별하는 문제가 됩니다.
4. 한 그룹에서 다른 그룹으로 중복없이 최대한 많이 매칭시킬 수 있는 알고리즘은 이분매칭을 사용하여 구하면 됩니다.

시간복잡도

O(N*N)

코드

#include<cstdio>
#include<string.h>
int n,k,e[51],f[51],t,i,j;
int r(int p){
    if(e[p])return 0;
    e[p]=1;
    for(int i=p;i<=n;i+=k){
        if(!f[i]||r(f[i])){
            f[i]=p;
            return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&k);
    for(;i<n;i++){
        memset(e,0,sizeof(e));
        scanf("%d",&t);
        j+=r(t);
    }
    printf("%d",j==n);
}