미소를뿌리는감자의 코딩
[백준 2024/01/20] 11047번 동전 0 본문
728x90
https://www.acmicpc.net/problem/11047
1. 접근 방법
이전에 동전과 관련된 문제를 푼 적이 있다.
당시엔 동전의 개수가 random이지 않았고, 500원 1000원 이런식으로 정해져 있던 것으로 생각이든다.
하지만, 이번 문제는 동전의 가치가 많았다.
1원이 있다는 점이 이 문제를 접근하기 쉽게 만들었다.
1원이 있다는 뜻은, 동전의 가치가 큰 것부터 나누기를 해나가며, 남은 부분을 1원으로 채우면 된다는 뜻이다.
이 부분을 깨닫고 난 후엔 쉽게 다가갈 수 있었다.
k원에 대해서 가치가 큰 동전으로 나눠나갔으며, 만약 몫이 0이라면 skip해주었다.
몫이 0이 아니라면 그 몫을 result에 저장해두고, 몫*동전의 가치를 k에서 빼주었다.
2. 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class b11047 {
public static void main(String[] args) throws IOException {
List<Integer> list = new ArrayList<>();
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String line = reader.readLine();
String[] num = line.split("\\s+");
int n = Integer.parseInt(num[0]);
int k = Integer.parseInt(num[1]);
for(int i =0; i<n;i++){
list.add(0,Integer.parseInt(reader.readLine()));
}
System.out.println(sum(list, k));
}
public static int sum(List<Integer> list, int k){
int result = 0;
int quotient;
for(int i=0; i<list.size(); i++) {
if ((k / list.get(i) != 0) ) {
quotient = k/list.get(i);
result += quotient;
k -= list.get(i)*quotient;
}
}
return result;
}
}
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/01/20] 1934번 최소공배수 + 유클리드 호제법 (0) | 2024.01.20 |
---|---|
[백준 2024/01/20] 11399번 ATM (0) | 2024.01.20 |
[백준 2024/01/20] 1037번 약수 (0) | 2024.01.20 |
[백준 2024/01/20] 1927번 최소 힙 (0) | 2024.01.20 |
[백준 2024/01/19] 11050번 이항 계수 1 (0) | 2024.01.19 |