Algorithm/boj
백준: 11047 동전 0
Mini_96
2022. 8. 12. 17:27
https://www.acmicpc.net/problem/11047
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
1. 정렬되있음->뒤에서부터 탐욕적으로 탐색
2. K보다 작거나 같은 최대값 선택
3.반복적으로 빼고, 카운트++
4.K==0이면 브레이크, 답 출력
5.현재 선택된값이 K보다 커지면 다시 탐욕적 탐색 , 3번으로가서 반복
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_11047_유동훈 {
static int N;
static int K;
static int[] arr;
static int count;
static int search()
{
for(int i=0;i<N-1;++i)
{
if(arr[i]<=K)
{
if(arr[i+1]<=K)
continue;
else
return i;
}
//else
//return 0;
}
return 0;
}
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//N = Integer.parseInt(br.readLine());
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N= Integer.parseInt(st.nextToken());
K= Integer.parseInt(st.nextToken());
arr=new int[N];
for(int i=0;i<N;++i)
{
arr[i]=Integer.parseInt(br.readLine());
}
//int current=arr[search()];
int index=0;
for(int i=N-1;i>=0;--i)
{
if(arr[i]<=K)
{
index=i;
break;
}
}
while(true)
{
if(K==0) break;
if(arr[index]>K)
{
for(int i=N-1;i>=0;--i)
{
if(arr[i]<=K)
{
index=i;
break;
}
}
}
K=K-arr[index];
count++;
}
System.out.println(count);
}
}