11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
#include <iostream>
#include <vector>
using namespace std;
int N, K;
vector<int> value;
int func()
{
int answer = 0;
int i = N-1;
do {
answer += (K / value[i]);
K %= value[i];
--i;
} while (i >= 0);
return answer;
}
int main()
{
cin >> N >> K;
int temp = 0;
for (int i = 0; i < N; ++i)
{
cin >> temp;
value.push_back(temp);
}
cout << func();
}
Greedy 알고리즘 문제로 간단하게 풀 수 있는 문제이다.
완전탐색을 진행하더라도 N번. 즉 10번만 돌면 되기 때문에 시간복잡도가 O(N)이다.
더보기
요즘 자꾸 주어진 케이스가 1개일 때 예외처리를 자꾸 빼먹는다. 문제 풀기 전에는 분명 꼭 1개일 때도 고려해야된다고 세번씩 다짐하지만 어느순간 잊는다.그래서 맨 위에 앞으로 주석으로 // N = 1개 일 때? 라고 추가하기로 했다.절대 안 볼 수 없게 특수문자 왕창 넣어 놔야지
'알고리즘 & 자료구조 > 백준' 카테고리의 다른 글
| [C/알고리즘] 백준 15828 (라우터) (0) | 2021.07.08 |
|---|---|
| [C++/알고리즘] 백준 2742 (기찍N) (0) | 2021.04.12 |
| [C++/알고리즘] 백준 1302 (베스트셀러) (0) | 2021.04.09 |
| [C++/알고리즘] 백준 1475 (방번호) (0) | 2021.04.08 |
| [C++/알고리즘] 백준 13904 (과제) (0) | 2020.10.18 |