[C] 백준 | 1010번 코드 - 다리 놓기

>문제

www.acmicpc.net/problem/1010

1010번: 다리 놓기

> 핵심

조합 (nCr)

https://terms.naver.com/entry.nhn?docId=3350149&cid=60210&categoryId=60210

>풀이과정

DP 문제라길래 풀어봤는데 막상 풀고나니까 DP보다는 조합 문제인 것 같다.

처음에는 DP처럼 풀려고 팩토리얼을 dp 배열에 저장해놓고 nCr 계산할 때 꺼내쓰려고 했었는데,

문제의 조건에 따르면 최대 30! 까지 구해야 할 수 있는데 이 30!은 unsigned long long 자료형을 사용해도 다 담을 수가 없는 범위이기 때문에 그렇게 할 수가 없다..!

 

그래서 그냥 반복문으로 계산하는 걸로 했다.

 

여기서 좀 쓸데없이 헤맸던 부분이 있는데

ans *= j / k

이렇게 하니까 답이 안나오는거.. 아무리 생각해도 조합 계산식이 맞는데 대체 왜 안돼지??

계산기로 일일히 해봤는데 맞게 나오는데 코드를 돌리면 답이 안나온다.

 

뭔가.. 했더니...

괄호를 안붙여줘서 그런거였다!!!!!!!!!!!!!!!!!!!

ans *= (j / k)
ans = ans * j / k

이렇게 하니까 정답이 나온다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

>깨달은점

확통을 안한지 가물가물해서 순열 조합도 잊고 살다가 이번에 다시 배워간다

 

조합은 컴비네이션. 뽑는 순서에 상관없이 때려박은 맛있는 피자같은 것.

이제 피자 시킬때 "조합피자 주세요" 라고 하자!

 

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
    int i, j, k, t, n, m;
    long long ans;
    scanf("%d", &t);

    for (i = 0; i < t; i++)
    {
        // mCn
        scanf(" %d %d", &n, &m);
        
        ans = 1;
        for (j = m - n + 1, k = 1; j <= m; j++, k++)
        {
            ans = ans * j / k;
        }

        printf("%lld\n", ans);
    }
    
    return 0;
}