๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/2775
- ์ด ์ํํธ์ ๊ฑฐ์ฃผ๋ฅผ ํ๋ ค๋ฉด ์กฐ๊ฑด์ด ์๋๋ฐ, “a์ธต์ bํธ์ ์ด๋ ค๋ฉด ์์ ์ ์๋(a-1)์ธต์ 1ํธ๋ถํฐ bํธ๊น์ง ์ฌ๋๋ค์ ์์ ํฉ๋งํผ ์ฌ๋๋ค์ ๋ฐ๋ ค์ ์ด์์ผ ํ๋ค” ๋ ๊ณ์ฝ ์กฐํญ์ ๊ผญ ์งํค๊ณ ๋ค์ด์์ผ ํ๋ค.
- ์ํํธ์ ๋น์ด์๋ ์ง์ ์๊ณ ๋ชจ๋ ๊ฑฐ์ฃผ๋ฏผ๋ค์ด ์ด ๊ณ์ฝ ์กฐ๊ฑด์ ์งํค๊ณ ์๋ค๊ณ ๊ฐ์ ํ์ ๋, ์ฃผ์ด์ง๋ ์์ ์ ์ k์ n์ ๋ํด k์ธต์ nํธ์๋ ๋ช ๋ช ์ด ์ด๊ณ ์๋์ง ์ถ๋ ฅํ๋ผ.
- ๋จ, ์ํํธ์๋ 0์ธต๋ถํฐ ์๊ณ ๊ฐ์ธต์๋ 1ํธ๋ถํฐ ์์ผ๋ฉฐ, 0์ธต์ iํธ์๋ i๋ช ์ด ์ฐ๋ค.
- ์ฒซ ๋ฒ์งธ ์ค์ Test case์ ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ๊ฐ๊ฐ์ ์ผ์ด์ค๋ง๋ค ์ ๋ ฅ์ผ๋ก ์ฒซ ๋ฒ์งธ ์ค์ ์ ์ k, ๋ ๋ฒ์งธ ์ค์ ์ ์ n์ด ์ฃผ์ด์ง๋ค.
- ๊ฐ๊ฐ์ Test case์ ๋ํด์ ํด๋น ์ง์ ๊ฑฐ์ฃผ๋ฏผ ์๋ฅผ ์ถ๋ ฅํ๋ผ.
์์ด๋์ด
- ์ด ๋ฌธ์ ๋ฅผ ๋ณด๊ณ ์ด๋ป๊ฒ ํ์ด์ผ ๋์ง ๊ณ ๋ฏผํ์๋ค... ๋๋ ๋ฐฐ์ด ๋๊ฐ๋ฅผ ๋๊ณ ํ์ด์ผ๊ฒ ๋ค๊ณ ์๊ฐํ๋ค.
- ์ฒซ๋ฒ์งธ 0์ธต์ ํธ์์ ์ธ์๋ค์ ์ ํด์ ธ ์์ผ๋ฏ๋ก ์ด๊ธฐ๊ฐ์ ์ ํด๋๊ณ ์์์ ํ๋ค.
- ๋ ๋ฐฐ์ด์ ํ์ฌ์ธต๊ณผ ์ ์ธต์ ์ธ์์๋ฅผ ์ ์ฅํ๋๋ฐ ์ฌ์ฉํ๋ค.
- ๋ฐ๋ณต๋ฌธ์ผ๋ก 1์ธต๋ถํฐ ๊ณ์ฐํ์์ผ๋ฉฐ ํ ์ธต์ ๊ณ์ฐํ๊ณ ๋์ ๋ค์์ธต์ผ๋ก ๋ ๊ฐ์ผ๋ ๊ฒฝ์ฐ, ํ์ฌ์ธต์ ์ธ์ ๊ฐ์ ์ ์ธต์ ๋ฐฐ์ด์ ํธ์์ ๋ง๊ฒ ๋ค์ ์ ์ฅํ๊ณ ํ์ฌ์ธต์ ๋ฐฐ์ด์ ๋ํด์๋ 1ํธ๋ ๊ณ์ 1๋ช ์ด๋ฏ๋ก 1๋ก ์ด๊ธฐํํด์ฃผ๊ณ ๋๋จธ์ง๋ 0์ผ๋ก ์ด๊ธฐํํด์ค๋ค.
- ํธ์๋ ๊ตฌํด์ผ ๋๋ ํธ์ nํธ๊น์ง๋ง ๊ตฌํ๋ฉด ๋๋ฏ๋ก n๋งํผ ๋ฐ๋ณตํด์ ๊ตฌํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- ์ฒ์์ ์๊ณ ๋ฆฌ์ฆ์ด ์๊ฐ๋์ง ์์ ์กฐ๊ธ ํค๋งธ์๋ค.. (์ฌ๋ด์ด์ง๋ง ์ ๋ฐ ๊ณ์ฝ์กฐ๊ฑด์ด ์์ผ๋ฉด ๋๊ฐ ์ ์ํํธ์ ๋ค์ด๊ฐ๊ณ ์ถ์๊น๋ ์๊ฐ์ด ๋ค์๋ค...ใ ใ )
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ2775 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int i = 0; i < T; i++){
int k = Integer.parseInt(br.readLine());
int n = Integer.parseInt(br.readLine());
// ์ ์ธต ์ธ์์๋ฅผ ์ ์ฅํ ๋ฐฐ์ด
int apt[] = new int[n + 1];
// ํ์ฌ์ธต ์ธ์์๋ฅผ ์ ์ฅํ ๋ฐฐ์ด
int apt2[] = new int[n + 1];
// 1ํธ๋ ๋ฌด์กฐ๊ฑด ์ธ์์ด 1๋ช
์ด๋ฏ๋ก 1๋ก ๊ณ ์
apt2[1] = 1;
for(int j = 1; j <= n; j++){
apt[j] = j;
}
// ํด๋น ์ธต์ด ๋ ๋๋ง๋ค ๋ฐ๋ณตํด์ผ๋๋ฏ๋ก
for(int j = 1; j <= k; j++){
// ํ ์ธต์ ํธ์๊ฐ ์ฌ๋ฌ๊ฐ์ด๋ฏ๋ก ํธ๋ง๋ค ๊ณ์ฐ
for(int l = 2; l <= n; l++){
// ํ ํธ์์ ๋ํด ์๋์ธต ์ธ์์๋ก ๊ณ์ฐ
for(int m = 1; m <= l; m++){
// ํ์ฌ ํธ์์ ์ธ์์์ ๊ตฌํด์ผ๋๋ ํธ์๊น์ง์ ์ ์ธต ์ธ์๋ค์ ๋ํด์ค
apt2[l] = apt2[l] + apt[m];
}
}
// ์ธต์ด ๋ง์ง๋ง ์ธต์ด๋ผ๋ฉด ์ข
๋ฃ
if(j == k) {
break;
}
// ๋ง์ง๋ง ์ธต์ด ์๋ ๊ฒฝ์ฐ
else{
for(int l = 1; l <= n; l++){
// ์ ์ธต์ ์ธ์์๋ค์ ํ์ฌ์ธต ์ธ์์ผ๋ก ์ด๊ธฐํ
apt[l] = apt2[l];
// ํ์ฌ์ธต ์ธ์์ ๋ฐฐ์ด์ ์ด๊ธฐํ
if(l == 1){
// 1์ธต์ ์ธ์์ด 1๋ช
์ด๋ฏ๋ก 1๋ก ์ด๊ธฐํ
apt2[l] = 1;
}
else{
// ๋๋จธ์ง๋ 0์ผ๋ก ์ด๊ธฐํ
apt2[l] = 0;
}
}
}
}
System.out.println(apt2[n]);
}
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 10989 ์ ์ ๋ ฌํ๊ธฐ 3 (0) | 2024.07.13 |
---|---|
[Java] BOJ 2869 ๋ฌํฝ์ด๋ ์ฌ๋ผ๊ฐ๊ณ ์ถ๋ค (2) | 2024.07.12 |
[Java] BOJ 2609 ์ต๋๊ณต์ฝ์์ ์ต์๊ณต๋ฐฐ์ (2) | 2024.07.12 |
[Java] BOJ 1546 ํ๊ท (2) | 2024.07.11 |
[Java] BOJ 1259 ํฐ๋ฆฐ๋๋กฌ์ (0) | 2024.07.11 |