[백준] 1010번: 다리 놓기 (C++)

조합과 중복의 개념이 오랜만이라

아래 사이트를 참고하여 내용을 복기시켰다

조합이 사용되므로 가장 간단한 공식은 다음과 같다

조합/중복 조합 계산기 | OurCalc

조합을 구현하기 위해 재귀 함수를 많이 사용하는 것 같지만

나는 반복문으로 시작한 김에

시간초과가 뜨더라도 답이 맞고 싶었다

하지만 마지막 예제에서 답이 계속 5가 곱해져서 나왔고

단순한 문제인 만큼 재귀 복습하는 셈치고 빨리 넘어갔다

반복문으로 시도한 코드는 다음과 같다

int main(){
    init();
    
    int t;
    cin >> t;
    
    int n, m;
    long long ans =  1;
    for(int i = 0; i < t; i++){
        cin >> n >> m;
        int m_temp = m;
        int n_temp = 1;
        
        for(int j = 0; j < n; j++){
            ans *= m_temp;
            ans /= n_temp;
            m_temp--;
            n_temp++;
        }
        
        cout << ans << '\n';
    }
    
    
}

input
>>>
3
2 2
1 5
13 29


output
>>>
1
5
339319575(answer: 67863915, 정확히 5배 차이)

놀랍게도 단순한 문제였다

int ans 가 초기화된 위치의 문제였다

1에서 5, 5에서 다음 숫자로 넘어가면서 초기화가 되지 않아서

정확히 5가 곱해진 것이다

그래도 해결했으니 다행이다

정신차리자!

 

// baekjoon 1010

#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>


using namespace std;

// codes for fast I/O
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}


int main(){
    init();
    
    int t;
    cin >> t;
    
    int n, m;
    for(int i = 0; i < t; i++){
        cin >> n >> m;
        
        int ans =  1;
        for(int j = 0; j < n; j++){
            ans *= (m - j);
            ans /= (1 + j);
        }
        
        cout << ans << '\n';
    }
    
    
}