[BOJ] 거스름돈 14916번 C++

 

 

문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

 

접근 방식

 

다양하게 풀 수 있는 문제인 것같다

그리디로 풀 수도있지만

나는 DP로 접근했다

 

DP배열을 -1로 초기화해주고

dp[2] = dp[5] = 1로 설정해준다

그리고 인덱스를 6부터 반복문을 돌면서

만약 dp[i-5] 값이 -1이 아니라면 dp[i] = dp[i-5]+1해주고

만약 dp[i-2]값이 -1이 아니라면

이 때 한가지 조건을 더 확인해준다.

만약 5동전을 사용하지 않고 2동전만으로 만들 수 있는 값이면

dp[i] = dp[i-2]+1해주고

그렇지 않다면 원래 dp[i]값과 dp[i-2]+1값과 비교해서 최소값을 설정해준다.

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int n;
int main() {
    cin>>n;
    int dp[100003];
    memset(dp, -1, sizeof(dp));
    dp[2] = 1;
    dp[4] = 2;
    dp[5] = 1;
    dp[0] = 0;

    for(int i=6; i<=n; i++) {
       if(dp[i-5] != -1) dp[i] = dp[i-5]+1;
       if(dp[i-2] != -1) {
        if(dp[i] == -1) dp[i] = dp[i-2]+1;
        else dp[i] = min(dp[i-2]+1, dp[i]);
       }
    }


    cout<<dp[n];
}