[백준] 11051번 - 이항 계수 2 (C++)

11051번: 이항 계수 2

 

문제

 

 

 

입력

 

 

출력

 

 

풀이과정

이항계수라는 문제의 기본 원칙은 위와 같은 형식으로 접근을 할 수 있는 문제였다.

위와 같은 점화식이 n, k 값이 들어오면 원하는 값을 도출해낼 수 있는 점화식이라고 해서

위와 같은 풀이식을 문제에 대입해서 풀어보았더니 이미 계산이 된 값에 % 10007을 진행하는 식으로 코드 진행이되어 런타임에러가 발생이 되었었다.

 

그래서 고민을 하다가 이항 계수라는 수 자체가 구하려는 수의 위에있는 2개의 수를 더하면 구할 수 있는 값이다보니

// 1
// 1 1
// 1 2 1
// 1 3 3 1

// dp[n][k] = dp[n - 1][k - 1] + dp[n - 1][k]

그대로 배열을 만들어서 구하려는 값 위쪽에 있는 2개의 값을 더하는 형식으로 코드를 구현하였습니다.

code

#include <iostream>

long long	f[1001][1001];


// dp[n][k] = dp[n - 1][k - 1] + dp[n - 1][k]
// 1
// 1 1
// 1 2 1
int		main(void)
{
	long long n, k;
	std::cin >> n >> k;

	f[0][0] = 1;
	f[1][0] = 1;
	f[1][1] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0 || j == i) f[i][j] = 1;
			f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % 10007;
		}
	}
	std::cout << f[n][k];

	return (0);
}

 

후기

처음에는 문제를 재귀로 접근을 했었는데
재귀로 접근을 재귀이다보니 같은 값을 또 구하는 상황이 발생이 되어 시간초과가 발생이 되었다.

dp문제를 접근할때는 dp자체가 원하는 값을 효율적으로 도출해내는 알고리즘이다보니까

재귀는 dp와 맞지않는다라는 생각을 가지게 되었다.