[백준] 14916_거스름돈 /C++/python

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

14916번: 거스름돈

이 문제는 한번 생각을 해보아야 한다.
무조건 5를 나누는게 아닌, 최소한의 개수를 구해야한다.
그래서 나는 처음에 1부터 계산 해보았다.

원	1	2	3	4	5	6	7	8	9
2원 개수	0	1	0	2	0	3	1	4	2
5원 개수	0	0	0	0	1	0	1	0	1

이렇게 보면,
5의 배수는 무조건 5원으로 나눈다.
그런데 2원은 무조건 2로 나눠진다고 해서 바뀌는게 아니였다.

원	10	11	12	13	14	15
2원 개수	0	3	1	4	2	0
5원 개수	2	1	2	1	2	3

생각해보면 쉽다.
5원까지는 미리 적어놔야하거나,
아니면 계산하면된다. -1이 있으니
5원부터는 앞에꺼 들고오는 식이다.

1. 또 여기서 10원 이하는 2의 몫이다.
2. 10이하의 홀수들은 배열[i-5]의 값에 +1을 하면된다.
왜냐면 5원을 빼면 2원이 남거든.
남은 걸 계산하지말고 들고오자!

이런것이다.
c++코드는 좀 오래전에 짜서

#include <iostream> using namespace std; int main() { int check[100001] = { -1,-1,1,-1,2, }; int num; int count = 0; cin >> num; for (int i = 5; i <= num; i++) { if (!check[i]) { if (i % 5 == 0) { check[i] = i / 5; } else { if (check[i - 5] == -1)check[i] = i / 2; else { check[i] = check[i-5] + 1; } } } } cout << check[num]; return 0; }

python

input_num = int(input()) check = [] for i in range(1,input_num+1): if (i%2 != 0) &(i %5 != 0) and i < 5: check.append(-1) else: if (i % 5 == 0): check.append(i//5) elif (i <10 and i % 2 == 0): check.append(i//2) else : check.append(check[i-6] + 1) print(check[input_num-1]) 

python 더 열심히 해보자.