์ค๊ท๊ฐ ๊ฐ์ง๊ณ ์๋ ๋์ ์ ์ด N์ข ๋ฅ์ด๊ณ , ๊ฐ๊ฐ์ ๋์ ์ ๋งค์ฐ ๋ง์ด ๊ฐ์ง๊ณ ์๋ค.
๋์ ์ ์ ์ ํ ์ฌ์ฉํด์ ๊ทธ ๊ฐ์น์ ํฉ์ K๋ก ๋ง๋ค๋ ค๊ณ ํ๋ค. ์ด๋ ํ์ํ ๋์ ๊ฐ์์ ์ต์๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N๊ณผ K๊ฐ ์ฃผ์ด์ง๋ค. (1 โค N โค 10, 1 โค K โค 100,000,000)
๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๋์ ์ ๊ฐ์น Ai๊ฐ ์ค๋ฆ์ฐจ์์ผ๋ก ์ฃผ์ด์ง๋ค. (1 โค Ai โค 1,000,000, A1 = 1, i โฅ 2์ธ ๊ฒฝ์ฐ์ Ai๋ Ai-1์ ๋ฐฐ์)
์ถ๋ ฅ
์ฒซ์งธ ์ค์ K์์ ๋ง๋๋๋ฐ ํ์ํ ๋์ ๊ฐ์์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค
๊ฐ์ฅ ํฐ ๋จ์์ ๋๋ถํฐ ๋๋๊ณ ๋นผ์ฃผ๊ธฐ
๊ฐ์ฅ ํฐ ๋จ์์ ๋๋ถํฐ ๋๋๊ณ ๋นผ์ฃผ๊ธฐ
count += (k/coin[i]);
k %= coin[i];
import java.io.*;
public class Greedy_1 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s[] = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int k = Integer.parseInt(s[1]);
int count = 0;
int coin[] = new int[n];
for(int i=0; i<n; i++)
coin[i] = Integer.parseInt(br.readLine().trim());
for(int i=n-1; i>=0; i--) {
if(k >= coin[i]) {
count += (k/coin[i]);
k %= coin[i];
}
}
System.out.println(count);
}
}
๋๋ฌด ์ฌ์...