[백준/BOJ] 17521번 Byte Coin (C++)

www.acmicpc.net/problem/17521

17521번: Byte Coin

그리디 문제 유형이라고 나오는데, 저는 DFS를 이용한 완전 탐색으로 매수/매도하는 모든 경우의 수를 구하고, 그 중에서 최대값을 구해 문제를 해결했습니다. 이때, 코인의 개수와 현금이 int 범위를 벗어날 수 있으므로 long long을 쓰는 것을 주의해야합니다. 

#include <iostream>
#include <vector>
using namespace std;

int n, w;
long long answer;
vector<int> v;

void DFS(int day, long long coin, long long cash) {
    if(day == n + 1) {
        answer = max(answer, cash);
        return;
    } else {
        for(int i = day; i <= n; i++) {
            long long num = cash / v[i]; // 매수 할 코인의 수 
            // 매수 
            DFS(i + 1, coin + num, cash - num*v[i]);
            // 매도 
            DFS(i + 1, coin - coin, cash + coin*v[i]);
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>w;
    v.resize(n + 1);
    for(int i = 1; i <= n; i++) {
        cin>>v[i];
    }

    DFS(1, 0, w); // day, countOfCoin, cash 
    cout<<answer;

}