https://www.acmicpc.net/problem/16395
λ¬Έμ
νμ€μΉΌμ μΌκ°νμ μ΄νκ³μλ₯Ό μΌκ°ν ννλ‘ λ°°μ΄ν κ²μΈλ°, λΈλ μ¦ νμ€μΉΌ(1623-1662)μ λ°λΌ μ΄λ¦ λΆμ¬μ‘λ€.
λ¨μν ννλ‘, νμ€μΉΌμ μΌκ°νμ λ€μκ³Ό κ°μ λ°©λ²μΌλ‘ λ§λ€ μ μλ€.
- Nλ²μ§Έ νμλ Nκ°μ μκ° μλ€.
- 첫 λ²μ§Έ νμ 1μ΄λ€.
- λ λ²μ§Έ νλΆν°, κ° νμ μ λμ κ°μ 1μ΄κ³ , λλ¨Έμ§ μμ κ°μ λ°λ‘ μ νμ μΈμ ν λ μμ ν©μ΄λ€.
μλ₯Ό λ€μ΄, n=3μ΄λ©΄ 3λ²μ§Έ νμ 2λ²μ§Έ μλ μ νμ μΈμ ν λ μ (1κ³Ό 1)μ λν΄μ λ§λ λ€.
n=6μΌ λ, νμ€μΉΌ μΌκ°νμ 6λ²μ§Έ νμ 10μ 5λ²μ§Έ νμ μΈμ ν λ μ(4μ 6)μ λν΄μ ꡬνλ€.
κ°μ λ°©μμΌλ‘ n=11μΌ λ, λ€μκ³Ό κ°μ νμ€μΉΌμ μΌκ°νμ λ§λ€ μ μλ€.
μ μ nκ³Ό kκ° μ£Όμ΄μ‘μ λ νμ€μΉΌμ μΌκ°νμ μλ nλ²μ§Έ νμμ kλ²μ§Έ μλ₯Ό μΆλ ₯νλ νλ‘κ·Έλ¨μ μμ±νμμ€. μ΄λ, μ΄ μλ μ΄νκ³μ C(n-1,k-1)μμ μ£Όμνμμ€.
μ λ ₯
첫째 μ€μ μ μ nκ³Ό kκ° λΉμΉΈμ μ¬μ΄μ λκ³ μ°¨λ‘λ‘ μ£Όμ΄μ§λ€. μ΄ λ, 1 ≤ k ≤ n ≤ 30μ λ§μ‘±νλ€.
μΆλ ₯
첫째 μ€μ nλ²μ§Έ νμ μλ kλ²μ§Έ μλ₯Ό μΆλ ₯νλ€.
νμ΄
μ΄νκ³μ 곡λΆνλ κ³ λ©λ λ°°μ΄ λ΄μ©μ΄κΈ΄ νμ§λ§
arr[n][k] = arr[n-1][k-1] + arr[n][k]
μ΄ μ μλ₯Ό μ΄μ©νμ¬ λ€μ΄λλ―Ή νλ‘κ·Έλλ° γ²
#include <iostream>
using namespace std;
int main () {
int n, k, arr[30][30];
cin >> n >> k;
arr[0][0] = 1;
for(int i=1; i<n; i++){
arr[i][0] = arr[i-1][0];
for(int j=1; j<i; j++){
arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
}
arr[i][i] = arr[i-1][i-1];
}
cout << arr[n-1][k-1];
return 0;
}
'π¦ Chango > π£ EDOC' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BOJ][C++] λ°±μ€ 11256λ²: μ¬ν (0) | 2021.11.16 |
---|---|
[BOJ][C++] λ°±μ€ 1058λ² : μΉκ΅¬ (0) | 2021.11.10 |
[BOJ][C++] λ°±μ€ 2670λ²: μ°μλΆλΆμ΅λκ³± (0) | 2021.11.03 |
[BOJ][C++] λ°±μ€ 2204λ²: λλΉμ λλ μ¦ ν μ€νΈ (0) | 2021.11.02 |
[BOJ][C++] 9946λ²: λ¨μ΄ νΌμ¦ (0) | 2021.11.02 |