백준 1010번 다리놓기

www.acmicpc.net/problem/1010

1010번: 다리 놓기

아ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ

AI 부캠 코테 준비하겠다고 1시간에 3문제 푸는 거 연습했는데,,,,꼴랑 한문제밖에 못풀었다,,,,,,

시험볼 때 엄청 긴장하는 체질인데 큰일이다,,,,,긴장안해도 한 문제라니,,,,

다리놓기 문제는 실버5라서 엄청 만만하게봤다. 딱 보자마자 ? 순열이네 역시~~ 이러면서 순열 코드를 짜고 돌렸는데 계속 시간초과가 뜨더라,,,,29C13같은 경우 답이 나오지도 않음 

이 문제에선 최대 수가 30인데 30!은 unsigned long long으로도 표현할 수 없을만큼 큰 숫자다.

그래서 시간초과가 뜨는 거다. -> 반대로 생각해보면 21! 정도는 long long으로 가능이다.

 

그럼 어떻게 하지,,,? 엄청 고민하면서 29C13이면 29 x 13 인 2차원 DP를 짜야되나? 고민했는데 규칙성이 안보였다.

 

답은 파스칼 삼각형,,, 내가 잘 알고있던거라 더 뭔가 통수맞은 기분이다. 

생각해보면 당연한 애기다. 고등학교 때 조합이라는 걸 배우면 파스칼의 삼각형이라는 게 같이 따라온다,,,, 

이걸 왜 생각 못했을까 ㅠㅠㅠ 심지어 최근에 파스칼 삼각형을 DP로 푸는 문제도 풀었었는데,,,,,

백준 1932 정수삼각형 ( blahblahlab.tistory.com/76?category=1172280 )

하지만 배우면 되는 거니까,,,이라고 자기합리화를 좀 해보자

 

✨조합 & 순열이 너무 큰 경우 -> 파스칼 삼각형을 DP로 구현✨

이 문제는 왼쪽의 m개의 점과 오른쪽 n개의 점을 겹치지않게 이어주는 경우의 수를 구해야한다.

m <= n이므로 그냥 n개에서 m개를 골라준 후 인덱스 순으로 이어주면 끝나는 문제라서 조합으로 풀 수 있다. 

파스칼의 삼각형을 이용하여 조합을 구현해보자면 

dp[i][j] 는 iCj를 의미한다. 점화식을 세워봄ㄴ 

 

j == 1일 때, iC1 = i -> DP[i][1] = i

j == 2 ~ i-1일 때, iCj =i-1Cj + i-1 C j-1 -> DP[i][j] = DP[i-1][j] + DP[i-1][j-1]

j == i일 떄, iCi = 1 -> DP[i][j] = 1

 

#include <iostream>
using namespace std;

int dp[30][30] = { 0 };

int main() {
	//dp 채우기
	dp[1][1] = 1;
	for (int i = 2; i < 30; i++) {
		dp[i][1] = i;
		for (int j = 2; j < i ; j++) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
		dp[i][i] = 1;
	}
	int tc;
	scanf("%d", &tc);

	
	for (int i = 0; i < tc; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		printf("%d\n", dp[y][x]);
	}
}