백준 문제 14916번 거스름돈

문제 출처:

https://www.acmicpc.net/problem/14916​

14916번: 거스름돈

백준  14916 번 거스름돈 문제

​이런 문제에 접근하기 전에 우선 예시를 들어보았다

    1  > -1
    2  > m2 = 1 
    3  > -1
    4  > m2 = 2
    5  > m5 = 1
    6  > m2 = 3
    7  > m5 = 1, m2 = 1
    8  > m2 = 4
    9  > m5 = 1, m2 = 2
    10 > m5 = 2
    11 > m5 = 1, m2 = 3
    12 > m5 = 2, m2 = 1
    13 > m5 = 2, m2 = 4
    14 > m5 = 2, m2 = 2
    15 > m5 = 3
    16 > m5 = 2, m2 = 3
    17 > m5 = 3, m2 = 1
    18 > m5 = 2, m2 = 4
    19 > m5 = 3, m2 = 2
    20 > m5 = 4

 

이런 식으로 동전으로 표현할 수 있는 최소한의 수를 세고 그 총합을 리턴하면 되는 문제이다.

​이 문제는 처음 주어진 n이라는 거스름돈을 5원으로 나눈 나머지, 2원으로 나눈 나머지를 잘 활용하여 풀어야 할 것이다.​

우선 내 코드는 이것이다.

//P_18512

#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio();
    cin.tie(NULL);
    cout.tie(NULL);

    int n, count ;
    unsigned short m5 = 0, m2 = 0;
    // n = a * m5 + b * m2
    // a + b < a_n + b_n
    // output -> a + b
    cin >> n ;

    if(n%5 != 0 && n%2 != 0 && n < 4){
        printf("-1\n");
        return 0 ;
    }
    else if(n%5 == 0){
        m5 = n/5 ;
    }
    else if(n%2 != 0){      // odd nember
        m5 += 1 ;
        n -= 5 ;
        m5 += (n / 10) * 2 ;
        m2 += (n % 10) / 2 ;
    }
    else{
        m5 += (n / 10) * 2 ;
        m2 += (n % 10) / 2 ;
    }
    
    count = m5 + m2 ;
    printf("%d\n", count) ;
    
    return 0;
}

생각해보면 간단한 문제인데 조금 오래걸렸다. 로직적인 부분을 작성하는 것이 제일 오래걸리는 것 같다.

​분발해야겠다.

 

해당 부분은 Github에서도 보실 수 있습니다.

https://github.com/gurcks8989/CodingTest/blob/master/BackJoon/HPS/P14916_RemainCoin.cpp

GitHub - gurcks8989/CodingTest: BackJoon_study_with_c++

 

훈수 및 조언은 언제든지 환영입니다.