글 읽기 - 이게 왜 DP일까요

andy627 7년 전 0

음... 일단 이 문제에서 왜 DP를 써야되는지를 모르겠고요...

이 코드가 WA가 뜨는데 어디가 틀렸거나 반례를 찾는데 도와주시면 감사하겠습니다!

#include <stdio.h>
#include <algorithm>
using namespace std;

int a[1111],b[1111];
bool used[1111];

int abs(int x){
    return x>0?x:-x;
}

int main(){
    int n,m,ans=0;

    scanf("%d %d",&n,&m);
    if(n>m){
        for(int i=0;i<n;i++) scanf("%d",&b[i]);
        for(int i=0;i<m;i++) scanf("%d",&a[i]);
        sort(a,a+m);
        sort(b,b+n);
    }
    else{
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        for(int i=0;i<m;i++) scanf("%d",&b[i]);
        sort(a,a+n);
        sort(b,b+m);
    }

    if(n>m) swap(n,m);

    for(int i=0;i<n;i++){
        int mn=1111111,pos;

        for(int j=0;j<m;j++){
            if(used[j]) continue;
            if(mn>abs(a[i]-b[j])){
                mn=abs(a[i]-b[j]);
                pos=j;
            }
        }

        ans+=mn;
        used[pos]=true;
    }

    printf("%d",ans);

    return 0;
}

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

문제

문제

출처

ICPC

이게 왜 DP일까요

andy627 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말