cpp) 백준 11050: 이항 계수 1

Problem

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

11050번: 이항 계수 1

자연수 N과 정수 K가 주어졌을 때 이항계수를 구하시오.

 

 

Solution

#include<iostream>
#include<string.h>
#include<algorithm>

using namespace std;

int cache[11][11];

int bino2(int n, int k){

    // 기저 사례
    if (k==0 || n==k)
        return 1;

    // cache[n][k] 값이 존재할 경우
    if (cache[n][k]!=-1){
        return cache[n][k];
    }
    
    return cache[n][k] = bino2(n-1,k-1) + bino2(n-1,k);
}

int main(){
    // ios::sync_with_stdio(0);
	// cin.tie(0); cout.tie(0);

    int n, k;
    cin >> n >> k;

    memset(cache, -1, sizeof(cache)); // 시작 주소, 세팅값, siezeof(데이터타입)=길이
    cout << bino2(n,k) << '\n';

    return 0; 
}

 

- memset(시작 주소, 세팅값, sizeof(데이터타입)) : cpp의 메모리를 초기화하는 함수, 헤더파일 string.h를 추가함.

- k가 0이거나 k=n일 때 기저 사례(base case, 더 이상 쪼개지지 않는 가장 작은 작업의 단위)

- 동적계획법(DP)은 이전에 계산했던 값을 cache에 저장하기 때문에 공간 복잡도는 늘리는 대신 시간 복잡도를 낮출 수 있다. 

 

 

Mechanism