[백준 1010번] 다리 놓기

 

 

목차

 

 

---

 

 

 

[백준 1010번] 다리 놓기

 

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

1010번: 다리 놓기

 

---

 

 

오답 코드

 

#include <stdio.h>

long long result[31];

int main()
{
    long long n, a, b, value;
    scanf("%lld", &n);
    
    for(int i=0; i<n; i++){
        scanf("%lld %lld", &a, &b);
        value = 1;
        for(long long j=b; j>=b-a+1; j--) value *= j;
        for(long long j=1; j<=a; j++) value /= j;
        result[i] = value;
    }
    
    for(int i=0; i<n; i++) {
        printf("%lld\n", result[i]);    
    }
    
    return 0;
}

시간초과

 

 

수정본

#include <stdio.h>

int main()
{
    int t, a, b, value;
    scanf("%d", &t);
    
    for(int i=0; i<t; i++){
        value=1;
        scanf("%d %d", &a, &b);
        
        for(int j=0; j<a; j++)
        {
        	value *= b-j;
        	value /= 1+j;
		}
		
		printf("%d\n", value);
    }
        
    return 0;
}

 

---

 

 

 

 

코드

 

#include <stdio.h>
using namespace std;

long long container[31][31];

long long DFS(int m, int r)
{
    if (container[m][r] > 0) return container[m][r];

    if (m == r || m == 1) return 1;
	if (r == 1) return m;

	return container[m][r] = DFS(m - 1, r) + DFS(m - 1, r - 1);
}

int main() {
    int t;
    scanf("%d", &t);

    int a, b;
    for (int i = 0; i < t; i++)
    {
        scanf("%d %d", &a, &b);

        printf("%lld\n", DFS(b, a));
    }

    return 0;
}

int 범위를 넘어가서 long long 사용.

 

long long contain[31][31]에 값을 담아 중복되는 값을 부를시 재귀없이 사용. 시간 단축 가능. 

 

 

---