정수론 및 조합론 - 11051번

2월 8일(수)-정수론 및 조합론(11051번)

11051번: 이항 계수 2

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 직전 11050번과 비슷하게 이항계수와 관련된 문제이지만, 동적계획법으로 구해야한다는 설명을 확인

- 11050번과의 차이점이 무엇인지 찾아보니, n의 범위가 1 ~ 10에서 1 ~ 1000까지로 변경되어있음

- 단순히 동적 메모리를 활용해서(malloc 혹은 calloc)을 활용하면 된다고 생각하고 코드작성을 시작함

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. 동적 메모리를 활용할 부분이 전혀 안보임

-> 무엇인가 잘못되었다는 생각을하고, 동적계획법에 대해서 검색해본 이후 해당 풀이에 대해서 알게됨

-> https://snupi.tistory.com/37

[C] 동적 계획법 (DP; Dynamic Programming)

2. top-down 방식의 동적계획법의 기본구조를 참고하여서 풀이를 어찌저찌 작성해보았지만, 완벽히 이해는 x

-> 참고1) https://snupi.tistory.com/80#recentComments

-> 참고2) https://velog.io/@inwooleeme/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-11051%EB%B2%88-%EC%9D%B4%ED%95%AD-%EA%B3%84%EC%88%98-2

 

3. dp[1001][1001]의 형태로 2차원 배열을 정적으로 선언해야하는 부분도 마음에 들지 않는다

-> 더 간단하게 바꿀 수 있는지 추후에 더 공부해봐야함

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SSECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int dp[1001][1001];

int cal(int n, int k)
{
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= k; j++)
		{
			if (i == j || j == 0)
			{
				dp[i][j] = 1;
			}
			else
			{
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007;
			}
		}
	}
	return dp[n][k];
}

int main(void)
{
	int n, k;
	scanf("%d %d", &n, &k);
	printf("%d", cal(n, k));

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ