Written by JS970
on October 30, 2022

1010 - 다리 놓기

난이도: 실버 5
날짜: 2022년 10월 30일
상태: Correct
추가 검토 여부: No

solution

문제를 읽어보면 결국 combination계산 한번으로 문제의 정답을 구할 수 있음을 알 수 있다.
최대 입력이 ${}{30}C{15}$이고 제한 시간은 0.5초이므로 일반적인 재귀 함수 형태로 구현하면 시간 내에 정답을 구할 수 없다.
조합의 기본 공식인 ${}{n}C{r} = {}{n-1}C{r-1} + {}{n-1}C{r}$을 사용하여 해결한다.
위 공식을 사용하여 재귀 함수로 구현하여도 제한 시간을 살짝 넘겨 오답을 출력했다.
전역 combination배열을 만들어 재귀 시마다 반복해서 연산하는 값을 저장한다.
이 방법을 사용하여 여러 번 호출되는 값의 중복 연산을 막을 수 있다.
전역 배열과 재귀 함수를 모두 사용하여 구현하니 정답을 출력했다.

code

#include <iostream>
using namespace std;

int combarr[31][31] {0, };

int combination(int total, int select)
{
    if (select == 0)
    {
        combarr[total][select] = 1;
        return 1;
    }
    else if (select == total)
    {
        combarr[total][select] = 1;
        return 1;
    }
    else
    {
        if(combarr[total][select] == 0)
            combarr[total][select]
							 = combination(total-1, select-1) + combination(total-1, select);
        return combarr[total][select];
    }
}

int main()
{
    int count;
    int N, M;
    cin >> count;
    while(count--)
    {
        cin >> N;
        cin >> M;
        cout << combination(M, N) << endl;
    }

    return 0;
}

# ref [1010번: 다리 놓기](https://www.acmicpc.net/problem/1010)

Top