#70. [백준_C언어] 1010 : 다리 놓기 \ 다이나믹 프로그래밍

 

입력 코드

#include <stdio.h>

double factorial(int n) {
	if (n == 1)
		return 1;

	return n * factorial(n - 1);
}

double combination(int N, int M) {
	if (M == 0 || M == N)
		return 1;

	return factorial(N) / (factorial(M)*factorial(N - M));
}

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

	int N, M;
	for (int i = 0; i < T; i++){
		scanf("%d %d", &N, &M);
		printf("%.f\n", combination(M, N));
	}
}

 

 

코드 설명

#수학 #다이나믹프로그래밍 #조합론

 

#include <stdio.h>

int factorial(int n) {
	if (n == 1)
		return 1;

	return n * factorial(n - 1);
}

int combination(int N, int M) {
	if (M == 0)
		return 1;

	return factorial(N) / (factorial(M)*factorial(N - M));
}

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

	int N, M;
	for (int i = 0; i < T; i++){
		scanf("%d %d", &N, &M);
		printf("%d\n", combination(M, N));
	}
}

nCm일 때 m==n이거나 m=0일 때 1을 반환함으로써 재귀함수의 종료문을 작성해야한다고 한다.

 

그리고 자료형도 변경해야 했다.

 

degurii.tistory.com/29

[BOJ] 백준 1010 다리 놓기

다리가 겹쳐지지 않도록 지어야하는데 어차피 조합으로 선택을 하면 된다.

 

 

재귀함수 대신에 조합의 성질을 이용하거나

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

double combination(int n, int m) {
	if (n == m)
		return 1;
	if (m == 1)
		return n;
	return combination(n - 1, m - 1) + combination(n - 1, m);
}

int main()
{
	int T, N, M;

	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		scanf("%d%d", &N, &M);
		printf("%.lf\n", combination(M, N));
	}

	return 0;
}

2차원 배열로 작성하는 방법도 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

long long c[30][30];

void combination() // n >= m
{
	for (int i = 1; i < 30; i++) {
		c[i][i] = 1;
		c[i][1] = i;
	}
	for (int i = 2; i < 30; i++) {
		for (int j = 2; j < 30; j++) {
			if (i>j)
				c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
		}
	}
}

int main()
{
	int T, N, M;
	scanf("%d", &T);

	combination();

	for (int i = 0; i < T; i++) {
		scanf("%d%d", &N, &M);
		printf("%lld\n", c[M][N]);
	}

	return 0;
}

 

다이나믹 프로그래밍을 통한 풀이 방법도 있다.

#include <stdio.h>

int main(){
    int qurry_n;
    int left, right;
    int result[31][31];
    
    for(int i = 1; i < 31; i++){
        result[i][i] = 1; // 동쪽과 서쪽 도시 개수가 같으면 다리를 잇는 방법은 하나
        for(int j = i + 1; j < 31; j++){
            result[i][j] = (i == 1 ? j : result[i][j-1] + result[i-1][j-1]); // 서쪽 도시가 하나면 다리를 잇는 방법은 동쪽 도시의 개수와 같다. 서쪽 도시가 하나 이상이면 다리를 잇는 방법은 동쪽 도시가 하나 적을 때 경우의 수 + 서쪽 동쪽 도시 모두 하나씩 적을 때 경우의 수이다.
        }
    }
    
    scanf("%d\n", &qurry_n);
    for(int i = 0; i < qurry_n; i++){
        scanf("\n%d %d\n", &left, &right);
        printf("%d\n", result[left][right]);
    }
    
    return 0;
}

terry1213.github.io/backjoon/1010-dynamic-programming/

[백준 1010번] 다리 놓기 - 다이나믹 프로그래밍(Dynamic programming)

 

 

References

jow1025.tistory.com/37

[백준 1010] 다리 놓기

wisdom-990629.tistory.com/entry/C-%EB%B0%B1%EC%A4%80-1010%EB%B2%88-%EB%8B%A4%EB%A6%AC-%EB%86%93%EA%B8%B0

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

 

 

 

문제 출처

www.acmicpc.net/problem/1010

1010번: 다리 놓기