๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/11047
- ์ค๊ท๊ฐ ๊ฐ์ง๊ณ ์๋ ๋์ ์ ์ด 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์์ ๋ง๋๋๋ฐ ํ์ํ ๋์ ๊ฐ์์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค.
์์ด๋์ด
- ๋์ ๊ฐ์น๋ฅผ ์ ์ฅํด์ ๋ฐฐ์ด์ ์ ์ฅ ํ, for๋ฌธ์ ํตํด ๋ฐฐ์ด์ ๋ค์์๋ถํฐ ์ฝ์ธ์ ๊ฐ์น์ ๋ง๋ค์ด์ผ๋๋ ๊ธ์ก์ ๋น๊ตํ๋ค.
- ๋ง์ฝ ์ฝ์ธ์ ๊ฐ์น๊ฐ ๋ง๋ค์ด์ผ ๋๋ ๊ธ์ก๋ณด๋ค ํด ๊ฒฝ์ฐ, ๋ค์ ๋ฐ๋ณต๋ฌธ์ผ๋ก ๋์ด๊ฐ์ ํ๋จ๊ณ ์์ ์ฝ์ธ์ ๊ฐ์น์ ๋ค์ ๋น๊ตํ๊ณ ์๊ฑฐ๋ ๊ฐ์ ๊ฒฝ์ฐ์๋ ๋ง๋ค์ด์ผ๋๋ ๊ธ์ก์ ํด๋น ์ฝ์ธ์ ๊ฐ์น๋ก ๋๋ ๋ชซ์ ๋์ ์ ๊ฐ์์ ๋ํด์ค๋ค.
- ๊ทธ๋ฆฌ๊ณ ๋ง๋ค์ด์ผ ๋๋ ๊ธ์ก์ ํด๋น ์ฝ์ธ์ ๊ฐ์น๋ก ๋๋ ๋๋จธ์ง ๊ฐ์ ๋ง๋ค์ด์ผ ๋๋ ๊ธ์ก์ผ๋ก ๊ฐฑ์ ์ํจ๋ค.
- ๊ทธ๋ ๊ฒ ๋ฐ๋ณตํ์ฌ ๊ธ์ก์ด 0์์ด ๋๋ฉด ๋ฐ๋ณต๋ฌธ์ ์ข ๋ฃํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- X
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ11047 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// ๋์ ์ ๊ฐ์
int N = Integer.parseInt(st.nextToken());
// ๋ง๋ค์ด์ผ๋๋ ๊ธ์ก
int K = Integer.parseInt(st.nextToken());
// ๋์ ๊ฐ์น ์ ์ฅํ ๋ฐฐ์ด
int coins[] = new int[N];
// ๊ฐ์ ์
๋ ฅ๋ฐ์ ๋ฐฐ์ด์ ์ ์ฅ
for(int i = 0; i < N; i++){
int c = Integer.parseInt(br.readLine());
coins[i] = c;
}
// ๋์ ๊ฐ์
int cnt = 0;
for(int i = N - 1; i >= 0; i--){
// ๋ง์ฝ ํด๋น ์ฝ์ธ ๊ฐ์น๊ฐ ๋ง๋ค์ด์ผ๋๋ ๊ธ์ก๋ณด๋ค ์๋ค๋ฉด
if(coins[i] <= K){
// ๋จ์ ๋ง๋ค์ด์ผ๋๋ ๊ธ์ก์ ์ฝ์ธ ๊ฐ์น๋ก ๋๋ ๋ชซ์
// ์ฝ์ธ ๊ฐ์์ ๋ํจ
cnt = cnt + (K / coins[i]);
// ๋จ์ ๊ธ์ก์ ํด๋น ์ฝ์ธ ๊ฐ์น๋ก ๋๋ ๋๋จธ์ง๋ก ๊ฐฑ์ ํจ
K = K % coins[i];
}
// ๋ง์ฝ ๋จ์ ๊ธ์ก์ด 0์ด ๋๋ฉด ๋ฐ๋ณต๋ฌธ ์ข
๋ฃ
if(K == 0){
break;
}
}
System.out.println(cnt);
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 17219 ๋น๋ฐ๋ฒํธ ์ฐพ๊ธฐ (6) | 2024.07.24 |
---|---|
[Java] BOJ 11399 ATM (2) | 2024.07.23 |
[Java] BOJ 1764 ๋ฃ๋ณด์ก (2) | 2024.07.23 |
[Java] BOJ 1874 ์คํ ์์ด (14) | 2024.07.23 |
[Java] BOJ 1654 ๋์ ์๋ฅด๊ธฐ (10) | 2024.07.22 |