๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/11050
- ์์ฐ์ ๊ณผ ์ ์ ๊ฐ ์ฃผ์ด์ก์ ๋ ์ดํญ ๊ณ์ ๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ์ฒซ์งธ ์ค์ ๊ณผ ๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ ≤ 10, 0 ≤ ≤ )
- ๋ฅผ ์ถ๋ ฅํ๋ค.
์์ด๋์ด
- ์กฐํฉ ๊ตฌํ๋ ๊ฒ์ด๋ฏ๋ก ๊ตฌํ๋ ์์ N! / (K! * (N - K)!) ์ด๋ค. ๋ฐ๋ผ์ ํฉํ ๋ฆฌ์ผ์ ๋ค ๊ณ์ฐํด์ ๋๋ ์๋ ์์ง๋ง K์ (N - K) ์ค์ ๋ ํฐ ๊ฐ์ ๊ตฌํด์ ๊ทธ ๊ฐ์ ํฉํ ๋ฆฌ์ผ ๊ฐ๋งํผ์ ์๊ณฑํ๊ณ ๊ทธ ๋ค์ ์๋ถํฐ N๊น์ง ๊ตฌํ ๋ค, ๋๋จธ์ง ๋ถ๋ชจ์ ํฉํ ๋ฆฌ์ผ ๊ฐ์ ๊ตฌํด์ ๋๋๋ฉด ๋ ๋น ๋ฅผ ๊ฒ์ด๋ผ๊ณ ์๊ฐํ๋ค.
- ์๋ฅผ ๋ค์ด (5 3)์ด๋ฉด ์์ด (5! / (3! * 2!)์ผ ๊ฒ์ธ๋ฐ 3์ด ๋ํฌ๋ฏ๋ก 5!์ ๊ณ์ฐํ ๋, 3!๋งํผ ์ ๊ณฑํด์ฃผ๊ณ ๋ถ๋ชจ์ ์๋ 3!์ ์์ ์ฃผ๋ฉด ๋๋ค. (1*2*3*4*5 / (1*2*3 * 2!)์ด๋ฏ๋ก ๊ณตํต๋ 1*2*3์ ์์ ์ฃผ๋ ๊ฒ์ด๋ค.) ๊ทธ๋ฆฌ๊ณ ๋จ์ 4*5 / 2!๋ง ๊ณ์ฐํด์ฃผ๋ฉด ๋๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- X (์ฒ์์ ๋ถ๋ฑํธ ์ค์๋ฅผ ํด์ ํ๋ฒ ํ๋ ธ์ง๋ง ๊ทธ๋๋ ๋๋ฆ ์ฝ๊ฒ ํ์๋ค ใ ใ )
์ฝ๋
import java.util.*;
import java.io.*;
public class BOJ11050 {
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());
// ์กฐํฉ์ ๊ตฌํ ๋ N! / (K! * (N-K)!)์ด๋ฏ๋ก
int K2 = N - K;
// ๊ฒฐ๊ณผ๊ฐ ์ ์ฅํ ๋ณ์
int result = 1;
// ํฉํ ๋ฆฌ์ผ ๊ณฑํ ๊ฐ ๊ตฌํ ๋ณ์
int mul = 1;
// ์กฐํฉ์ ๊ตฌํ ๋ ๋๋๋ ๊ฒ์ด K!๊ณผ (N-K)!์ด๋ฏ๋ก ๋ ํฐ์ชฝ์ ๊ธฐ์ค์ผ๋ก
if(K >= K2){
// ํฉํ ๋ฆฌ์ผ์ด 1๋ถํฐ ํด๋น ์๊น์ง ๋ชจ๋ ๊ณฑํ๋ ๊ฒ์ด๊ธฐ ๋๋ฌธ์
// ์ด์ฐจํผ ๋๋ ์ผ ๋ ์๋ผ๋ฉด ์ฒ์๋ถํฐ ์๊ณฑํ๋๋ก
// ๋ ํฐ์๋ณด๋ค ํฐ์๋ถํฐ N๊น์ง ๊ณฑํด์ ์ ์ฅ
for(int i = (K + 1); i <= N; i++){
result = result * i;
}
// ๋๋จธ์ง ์์ ๊ฐ์ ํฉํ ๋ฆฌ์ผ ๊ณ์ฐํด์ค
for(int i = 1; i <= K2; i++){
mul = mul * i;
}
// ์์ ๊ณฑํ์๋ฅผ ์์ ๊ฐ์ ํฉํ ๋ฆฌ์ผ ๊ณ์ฐํ ๊ฐ์ผ๋ก ๋๋ ์ค
result = result / mul;
}
// ์์ ๊ฐ์ ๋ฐฉ์
if(K2 > K){
for(int i = (K2 + 1); i <= N; i++){
result = result * i;
}
for(int i = 1; i <= K; i++){
mul = mul * i;
}
result = result / mul;
}
System.out.println(result);
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 1181 ๋จ์ด ์ ๋ ฌ (2) | 2024.07.14 |
---|---|
[Java] BOJ 28702 FizzBuzz (0) | 2024.07.13 |
[Java] BOJ 10989 ์ ์ ๋ ฌํ๊ธฐ 3 (0) | 2024.07.13 |
[Java] BOJ 2869 ๋ฌํฝ์ด๋ ์ฌ๋ผ๊ฐ๊ณ ์ถ๋ค (2) | 2024.07.12 |
[Java] BOJ 2775 ๋ถ๋ ํ์ฅ์ด ๋ ํ ์ผ (0) | 2024.07.12 |