[백준] 1010번: 다리 놓기

 

 

---

 

문제

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

 

 

개념

수학(조합), 다이나믹 프로그래밍

 

 

실행 결과

 

 

 

 

구현 코드(c++)

#include <iostream>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int t;
  cin >> t;

  while (t--) {
    int n, m;
    cin >> n >> m;
    unsigned long long res = 1;
    for (int i = 0; i < n; i++) {
      res *= (m - i);
      res /= (i + 1);
    }
    cout << res << endl;
  }
}

 

 

 

 

코드 설명

단순히 조합 mCn을 계산하는 문제이다.

처음에는 공식을 사용하여 단순 계산식을 만들었으나 시간 초과로 실패하거나 메모리 에러가 발생했다.

출처: 코딩팩토리(https://coding-factory.tistory.com/606#google_vignette)

문제에서 m이 n보다 항상 크다고 주어지므로 공식의 n을 m으로, r을 n으로 두었다.

여기서 시간복잡도를 줄이려면 중복 연산을 없애면 된다. m!과 m-n!은 계산 과정에서 반드시 약분되기 때문이다. 

 

 

m=7, n=3이라고 했을때 다음과 같은 규칙이 나온다.

이를 바탕으로 세운 식은 다음과 같다. 

for (int i = 0; i < n; i++) {
  res *= (m - i);
  res /= (i + 1);
}

 

분자 부분은 곱해주고 분모 부분은 나눠주면 한 번에 계산할 수 있다.

또한 결국 조합 문제이기 때문에, DP로도 풀 수 있다. 하지만 위 방법이 훨씬 간단하다..!

 

 

 

---