[12865] - DP를 통한 접근

그렇다 .. 처음 접근 했을때 ... 못풀었다 ㅋㅋㅋㅋㅋㅋㅋ 처음에 접근 방식을 완전 탐색? 뭐 이렇게 생각을 했었는데 

전에 문해기 시간 때 했던 DP와 비슷한 접근이었다. 이 유형의 문제가 DP의 2가지중 하나의 대표적 유형이라고 한다.(힙색이었나? 배낭DP라고 했던듯 ...)

일단 내 코드다. 

#include<iostream>

#include<string.h>

using namespace std;

long long  arr[100001];

long int dp[100001];

int main(){

    int num;

    int weight;

    

    memset(dp,0,sizeof(dp));

    memset(arr,0,sizeof(arr));

    

    cin >> num >> weight;

    

    for(int i=1;i<=num;i++){

        int a,b;

        cin >> a >> b;

        arr[i] =a*1000000LL+b;                //각각의 숫자를 저장하기 위해(a,b를 구분하기 위해) 사용.

    }                                         //a*10000 뒤에 LL을 붙임으로서 자동적으로 형변환을 사용

    

    for(int i=1;i<=num;i++){

        long int q = arr[i]/1000000;

        long int w = arr[i]%1000000;

        for( int j=weight;j>=q;j--){        //뒤에서 부터 반복한다!! - 중복되는 경우를 막기위해서!

            if(w+dp[j-q]>dp[j]){            //업데이트 과정인데 ... 음 ... 뭐랄까 ....

                dp[j] = w+dp[j-q];

            }

        }

    }

    

    cout << dp[weight] << endl;

}

음 .. 이렇다ㅎㅎ 뒤에서 부터 채우면서 3에서 7을 만드려면 4을 더해야 하고, 6이되려면 3을 더해야 하고 이런 방식이다. 

깔끔한 코드를 보자면 

	#include <stdio.h> #include <algorithm>
	using namespace std;
	int w[100], v[100];
	int d[100000];
	int main()
	{
	int N, K; scanf("%d %d", &N, &K);
	for(int i = 0; i < N; i++)
	scanf("%d %d", &w[i], &v[i]);
	for(int i = 0; i < N; i++)
	for(int k = K; w[i] <= k; k--)
	d[k] = max(d[k], d[k - w[i]] + v[i]);
	printf("%d\n", d[K]);
	return 0;
	}

크 깔끔하다 .... 물론 같은 로직이긴한데 훨씬 깔끔하고 간단해서 실수를 줄일수 있을듯한 코드이다.