[백준][1073번][DP] 도미노

도미노 

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

<코드>

#include <stdio.h>
 
int map[11][11];
int numbers[10];
 
int main(void){
 
    int number;
    int d[10] = { 1, 0, 1, 0, 3, 0, 15, 0, 105, 0 };
    scanf("%d", &number);
 
    for (int i = 0; i < number; i++){
        int temp;
        int a, b;
        scanf("%d", &temp);
        a = temp / 10;
        b = temp % 10;
        numbers[a]++;
        numbers[b]++;
    }
 
 
    long long result=1;
 
 
    for (int i = 0; i < 10; i++)
    {
        result *= d[numbers[i]];
    }
 
    printf("%lld\n", result);
 
    return 0;
}

<문제 푼 요령>

 요령에 앞서서 이 문제 같은 경우는 문제를 스스로 풀지 못해서 답지를 봐도 답이 없어서 이해가 매우 어려웠다.

1. 이 문제는 그래프 문제 오일러 회로에 대한 이해가 있으면 편할 듯 싶다. 한 붓 그리기와 유사

2. 오일로 회로가 존재하려면, 모든 정점의 차수는 짝수여야한다.

3. 어떤 정점을 방문했을 때, 사용한 간선과 다른 간선 하나가 쌍으로 존재해야 한다. 

4. 차수가 x인 노드에서 가능한 쌍의 개수가 d[x] 이면 d[x] = (x-1) * d[x-2]

이 4번이 이해가 오래걸렸다. 좀 더 편한 이해를 위해 아래의 그림을 만들어 보았다.

 (1). 간선이 2개를 가진 접점일 때

 위의 경우는 간선이 두개 인데 하나는 들어가야 하기 때문에 나 올 수 있는 경우의 수는 1개가 된다.

 (2) 간선이 4개를 가진 접점일 때

위 그림이 핵심이다. 즉 접점에 들어가면 다음으로 이동해야 하는 경우의 수는 들어갔던 간선의 수를 제외 해야하기 때문에 총 간선의 수가 x 라면 경우의 수는 x-1 이 된다. 그리고 중요한 요소 중 하나가 사용한 간선과 다른 간선은 쌍으로 존재하기 때문에 다시 이 접점에 들어가면 남는 경우의 수는 간선이 2개일 때의 경우의 수와 같아지는 것이다. 

 즉 D[n]이 간선에 가지 수 에 대해서 나올 수 있는 총 개수라고 하면 D[n] = (x-1) * D[x-2] 가 되는것이다.

5. 즉 D[n]을 구한다면 모든 정점에 대해서 구한 D[n]을 곱해주면 된다. 그렇다면 최종 경우의 수가 나오게 되는 것이다.