[BaekJoon][1613] 역사

BAEKJOON ONLINE JUDGE

1613 역사

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

1. dfs

모든 -1 중에서 새롭게 만들 수 있는 -1을 모두 탐색

#include <cstdio>
#include <algorithm>
using namespace std;
 
struct Number {
    int num, idx;
};
 
int n;
Number num[100001];
 
bool cmp(const Number &first, const Number &second)
{
    return first.num < second.num;
}
 
int main()
{
    int m;
    int i, j;
    int s, e, k;
 
    scanf("%d %d", &n, &m);
 
    for (i = 1; i <= n; i++) {
        scanf("%d", &num[i].num);
        num[i].idx = i;
    }
 
    sort(num + 1, num + n + 1, cmp);
 
    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &s, &e, &k);
 
        int cnt = 0;
        for (j = 1; j <= n; j++) {
            if (num[j].idx >= s && num[j].idx <= e)    cnt++;
            if (cnt == k)    {
                printf("%d\n", num[j].num);
                break;    
            }
        }
    }
 
    return 0;
}

2. 플로이드 와샬

#include <stdio.h>
 
int n;
int history[401][401];
 
void solve()
{
    int i, j, k;
 
    for (k = 1; k <= n; k++) {
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                if (history[i][j] == 0) {
                    if (history[i][k] + history[k][j] == 0);
                    else if (history[i][k] == -1 && history[k][j] == -1)
                        history[i][j] = -1;
                    else if (history[i][k] == 1 && history[k][j] == 1)
                        history[i][j] = 1;
                }
            }
        }
    }
}
 
int main()
{
    int m;
    int i;
    int before, after;
 
    scanf("%d %d", &n, &m);
    for (i = 0; i < m; i++) {
        scanf("%d %d", &before, &after);
        history[before][after] = -1;
        history[after][before] = 1;
    }
 
    solve();
 
    scanf("%d", &m);
    for (i = 0; i < m; i++) {
        scanf("%d %d", &before, &after);
        printf("%d\n", history[before][after]);
    }
 
    return 0;
}