Loading [MathJax]/jax/output/CommonHTML/jax.js

본문 바로가기

그리디

(2)

[백준] 11399번: ATM - JAVA 🔗 문제 링크 BOJ 11399번: ATM 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 📝 풀이 과정 사람들이 번호 순서대로 줄을 선 상태이고, [3, 1, 4, 3, 2]의 인출시간이 걸린다고 했을 때, 아래만큼의 시간이 각각 소요되게 된다. 0번 : 3= 3 1번 : 3 + 1= 4 2번 : 3 + 1 + 4= 8 3번 : 3 + 1 + 4 + 3= 11 4번 : 3 + 1 + 4 + 3 + 2= 13 -------------------------------------- 총 인출 시간 : 3 + 4 + 8 + 11 + 13 = 39 ..

[백준] 11047번: 동전 0 - JAVA 🔗 문제 링크 BOJ 11047번: 동전 0 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 📝 풀이 과정

$A_i$ 가

$A_{i-1}$ 의 배수이기 때문에 그리디로 문제를 해결할 수 있다. 동전의 가치가 큰 순서대로 K값을 넘지 않는 최대 개수만큼 값을 빼주면서 K = 0일 때까지 계산하면 되는 문제이다. 동전(A)이 오름차순으로 입력이 주어지기 때문에, 반복문을 i = n - 1로 시작해 역순으로 진행하면 된다. 종료 조건은 2가지를 걸어주었는데..

티스토리툴바