[Algorithm] ๐๋ฐฑ์ค 11047 ๋์ 0
0. ๋ฌธ์
์ค๊ท๊ฐ ๊ฐ์ง๊ณ ์๋ ๋์ ์ ์ด 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์์ ๋ง๋๋๋ฐ ํ์ํ ๋์ ๊ฐ์์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค
1. ์์ด๋์ด
๊ฐ์ฅ ํฐ ๋จ์์ ๋๋ถํฐ ๋๋๊ณ ๋นผ์ฃผ๊ธฐ
2. ํต์ฌ ํ์ด
๊ฐ์ฅ ํฐ ๋จ์์ ๋๋ถํฐ ๋๋๊ณ ๋นผ์ฃผ๊ธฐ
count += (k/coin[i]);
k %= coin[i];
3. ์ฝ๋
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);
}
}
4. ๊ฒฐ๊ณผ
๋๋ฌด ์ฌ์...
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐๋ฐฑ์ค 11047 ๋์ 0), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-๋ฐฑ์ค-11047-๋์ -0์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค