[백준/C++] 1010번. 다리 놓기

문제

1010번: 다리 놓기

---

1. 마지막 풀이

사고 과정

DP로 풀면 쉽게 풀릴 것 같았다. 조합의 특성이 딱 맞기 때문에.

 

조합의 계산식을 예시와 함께 살펴보겠다.

 

6C2는 식으로 쓰면, 위와 같이 쓰인다.

 

 

이건 이 식을 변형한 것으로, n!을 (n - r)!로 약분해서 만든 형태다.

 

그럼 7C2는 어떻게 표현될까?

 

 

7C2는 위처럼 표현된다. 마지막 숫자가 나눠지고, n이 그대로 곱해진다.

이를 좀 더 수학적으로 표현해보면 아래처럼 나타난다.

 

 

이는 그대로 DP로 구현된다. 바로 코드를 살펴보자.

 

코드

#include <iostream>
#include <vector>

int main() {
	int t;
	std::cin >> t;

	while (t--) {
		int n, m;
		std::cin >> n >> m;

		std::vector<int> dp(m + 1, 0);
		dp[n] = 1;

		for (int i = n + 1; i <= m; i++) {
			dp[i] = dp[i - 1] * i / (i - n);
		}

		std::cout << dp[m] << "\n";
	}
}

 

결과

가볍게 성공했다. 딱히 어려운 부분은 없으니 설명은 더 하지 않겠다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/30821097

bini0823님의 코드. 원리는 동일하다.

 

내 코드와 비교

이 분은 배열을 사용하는 대신, int a를 선언한 후 여기에 위 수식을 반복하는 방식으로 푸셨다.

배열을 쓰지 않는 만큼 메모리를 절약할 수 있어 더 효율적인 것 같다.

---

강평

나는 조합을 풀 때 항상 이 방법을 사용했기에, 운 좋게 쉽게 풀 수 있었다. 그러나 문제 분류에 낚여 굳이 배열을 쓰고 말았다. 변수 하나로도 끝나는 걸 굳이 배열을 쓴 점이 가장 아쉬웠다.