[SWEA 1259] 금속 막대

문제 출저 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18NaZqIt8CFAZN

 

풀이 : 

 

DP문제라고 해서 보긴 했는데 DP로 푸는방법이 떠오르진 않네요 ㅠㅠ

혹시 DP로 푸신분있으면 가르쳐 주시면 감사하겠습니다...

 

너무 야매로 푼거같아서 어떤 알고리즘으로 풀었다고 해야 할 지 모르겠네요...

 

일단 이 문제는 수나사와 암나사의 사이즈를 맞춰서 최대로 연결하는 문제입니다.

문제의 조건이 너무 불충분해서 제가 테스트 케이스로만 분석하여

수나사와 암나사의 최대 크기는 30, 금속 막대의 개수는 20개로 놓고 풀었습니다.

 

그다음 마찬가지로 조건이 너무 불충분 하여 두가지 가정을 하였습니다.

가정 1) 모든 나사는 짝이 있다.

가정 2) 암나사나 수나사의 크기가 같은 금속 막대는 없다.

 

이러한 가정을 바탕으로 저는 크기가 30인 check 배열을 선언해 수나사는 ++, 암나사는 --를 해주었습니다.

이렇게 했을 시 좋은 점은 짝이 있는 나사들은 배열의 값이 0이 되고 맨 앞의 수나사는 1, 맨 뒤의 암나사는 -1이 되기 때문에 시작과 끝 점을 찾는 과정을 진행할 필요가 없어집니다.

 

따라서 모든 막대에 대해 위의 풀이를 적용하고 맨 앞의 수나사부터 맨 뒤의 암나사 까지 출력을 하면 끝입니다.

 

 

#include<stdio.h>
 
int t, n,cache[31],check[31],front,rear;
 
int main()
{
    scanf("%d", &t);
    for (int test = 1; test <= t; test++)
    {
        printf("#%d ", test);
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            scanf("%d %d", &front, &rear);
            cache[front] = rear;
            check[front]++;
            check[rear]--;
        }
        for (int i = 1; i <= 30; i++)
        {
            if (check[i] == 1)front = i;
            if (check[i] == -1)rear = i;
            check[i] = 0;
        }
        while (1)
        {
            printf("%d %d ", front, cache[front]);
            front = cache[front];
            if (front == rear)
            {
                printf("\n");
                break;
            }
        }
    }
}