티스토리 뷰
반응형
문제 링크: www.acmicpc.net/problem/1398
1, 10, 25, 100, 1000, 2500, 10000, 100000, ...
화폐단위가 100씩 곱한 값으로 끊어진다는 것을 캐치하면 쉽게 풀리는 문제이다.
현재 지불해야하는 금액 중 100으로 나눈 나머지는 어차피 100 이하의 금액인 동전(1, 10, 25)로만 지불할 수 밖에 없다.
따라서 1~99 금액에 대한 필요한 동전 개수를 계산해 dp배열에 저장해두고 지불해야 하는 금액의 100으로 나눈 나머지에 대해 필요한 동전 개수를 더해나간다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int t; // 테스트케이스 개수
long long ans;
long long price;
int dp[100];
// dp 배열 값 계산
void calc() {
for (int i = 0; i < 100; i++) {
if (i >= 25) {
dp[i] = min(dp[i - 25] + 1, dp[i - 10] + 1);
dp[i] = min(dp[i], dp[i - 1] + 1);
}
else if (i >= 10) {
dp[i] = min(dp[i - 10] + 1, dp[i - 1] + 1);
}
else{
dp[i] = i;
}
}
}
// 화폐 단위가 100단위로 곱해진다는 것에 주목 {1,10,25}*(100^k)
void solve() {
long long tmp = price % 100;
ans += dp[tmp];
price /= 100;
if (price > 0) {
solve();
}
}
int main() {
// dp 배열 계산하고 시작
memset(dp, 100, sizeof(dp));
calc();
scanf("%d", &t);
for (int i = 0; i < t; i++) {
scanf("%lld", &price);
ans = 0;
solve();
printf("%lld\n", ans);
}
return 0;
}
반응형
'알고리즘 > Baekjoon' 카테고리의 다른 글
백준 1662: 압축 (C++) (0) | 2020.11.25 |
---|---|
백준 1463: 1로 만들기 (C++) (0) | 2020.11.25 |
백준 1918: 후위 표기식 (C++) (0) | 2020.11.22 |
백준 4949: 균형잡힌 세상 (C++) (0) | 2020.11.21 |
백준 2164: 카드2 (C++) (0) | 2020.11.21 |
댓글
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 백준
- React
- 카카오추천팀
- reactjs
- MySQL
- dash-plotly
- 프로그래머스
- 자료구조
- 회고
- 코테후기
- 개발
- c++
- 컴퓨터공학
- 자바스크립트
- 리액트
- 다이나믹프로그래밍
- 우선순위큐
- 코드포매터
- Dash
- 알고리즘
- 머신러닝
- plotly
- 컴퓨터과학
- JS
- 큐
- 동적계획법
- 스택
- dfs
- sql
- 후위표기식
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함