2016.03.24 모임 51

지난 주에 이어 계속 됩니다.

활동 일시: 03월 24일 (목) 18:32 - 20:30
모임 장소: 강남 R&D 캠퍼스 1층 회의실
활동 주제: dynamic programming

문제 링크

오답이 SUSHI 나오는 소스코드 입니다.

#include <iostream>

using namespace std;

int n, m;
long long price[20], sat[20];
long long memo[201] = { 0, }  ; // 0 ~ 200

void calc() {
    for (int i = 1; i <= m; i++) {
        long long temp = 0;

        for (int j = 0; j < n; j++) {
            if (0 <= i-price[j]) {
                temp = memo[(i-price[j]) % 201] + sat[j];
            }
            memo[i % 201] = max(memo[i % 201], temp);
        }
    }
}

int main() {
    int t; cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
            cin >> price[i] >> sat[i];
            price[i] /= 100;
        }
        m /= 100;

        calc();
        cout << memo[m % 201] << endl;
    }
    return 0;
}

memo 를 초기화 해 주니까 답이 나오는군요 @.@

#include <iostream>

using namespace std;

const int SIZE = 0xFF;

int n, m;
int price[20], sat[20];
int memo[SIZE] = { 0, }  ; // 0 ~ 200

void calc() {
    memo[0] = 0;
    int best = 0;
    for (int i = 1; i <= m; i++) {
        int &now = memo[i & SIZE];
        now = 0;
        for (int j = 0; j < n; j++) {
            if (0 <= i-price[j]) {
                int temp = memo[(i-price[j]) & SIZE] + sat[j];
                now = max(now, temp);
            }
        }
        best = max(best, now);
    }
    cout << best << endl;
}

int main() {
    int t; cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
            cin >> price[i] >> sat[i];
            price[i] /= 100;
        }
        m /= 100;

        calc();
    }
    return 0;
}

사진

Written on March 11, 2016