백준 14916 - 거스름돈(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14916

14916번: 거스름돈

N원을 2원과 5원으로 거슬러줄때, 최소 동전의 개수를 구하는 문제입니다.

 

2원과 5원으로 나눠주기에 주지 못하는 값은 -1로 출력하면 됩니다.

 

배열의 2와 5칸의 값을 1로 만들어준뒤, N원까지 차례대로 동전의 개수를 구하면 됩니다.

 

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int N;
int dx[100001];

void solve(){
    dx[5] = 1;
    dx[2] = 1;
    for(int i = 3; i <= N; i++){
        if(dx[i-2] > 0) dx[i] = dx[i-2] + 1;
        if(dx[i-5] > 0) dx[i] = min(dx[i], dx[i-5] + 1);
    }
    if(dx[N] > 0) cout << dx[N];
    else cout << "-1";
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.