πŸ“¦ Chango/🍣 EDOC

[BOJ][C++] 16395번: νŒŒμŠ€ν‚¬μ˜ μ‚Όκ°ν˜•

선달 2021. 11. 3. 08:34
λ°˜μ‘ν˜•

https://www.acmicpc.net/problem/16395

 

16395번: 파슀칼의 μ‚Όκ°ν˜•

파슀칼의 μ‚Όκ°ν˜•μ€ μ΄ν•­κ³„μˆ˜λ₯Ό μ‚Όκ°ν˜• ν˜•νƒœλ‘œ λ°°μ—΄ν•œ 것인데, λΈ”λ ˆμ¦ˆ 파슀칼(1623-1662)을 따라 μ΄λ¦„ λΆ™μ—¬μ‘Œλ‹€. λ‹¨μˆœν•œ ν˜•νƒœλ‘œ, 파슀칼의 μ‚Όκ°ν˜•μ€ λ‹€μŒκ³Ό 같은 λ°©λ²•μœΌλ‘œ λ§Œλ“€ 수 μžˆλ‹€. N번째 ν–‰

www.acmicpc.net

 

문제

파슀칼의 μ‚Όκ°ν˜•μ€ μ΄ν•­κ³„μˆ˜λ₯Ό μ‚Όκ°ν˜• ν˜•νƒœλ‘œ λ°°μ—΄ν•œ 것인데, λΈ”λ ˆμ¦ˆ 파슀칼(1623-1662)을 따라 μ΄λ¦„ λΆ™μ—¬μ‘Œλ‹€.

λ‹¨μˆœν•œ ν˜•νƒœλ‘œ, 파슀칼의 μ‚Όκ°ν˜•μ€ λ‹€μŒκ³Ό 같은 λ°©λ²•μœΌλ‘œ λ§Œλ“€ 수 μžˆλ‹€.

  1. N번째 ν–‰μ—λŠ” N개의 μˆ˜κ°€ μžˆλ‹€.
  2. 첫 번째 행은 1이닀.
  3. 두 번째 ν–‰λΆ€ν„°, 각 ν–‰μ˜ μ–‘ 끝의 값은 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;
}

 

 

λ°˜μ‘ν˜•