[Codeforces] Codeforces Round #408 (Div. 2) 이야기

이번 #408대회는 점수를 좀 더 올릴 수 있었는데 +13점 밖에 못올렸다.

1, 2번 문제를 풀었는데 1번 문제, 2번 문제를 빨리 풀었다. 

하지만 2번 문제에 실수가 있다는 걸 나중에 깨닫고 다시 푼 결과 

1시간 10분정도 후에 최종적으로 내게되어 많은 패널티를 받게 되고 결국 2번 문제의 점수를 많이 받지 못하였다.

이번 대회에서는 그래도 만족스럽게 느껴지는 것이, 예전보다 해석에 대해 덜 부담스럽게 되었고, 문제를 4번까지 볼 수 있었다.

(물론 못풀었지만.)

A번 문제는 다음과 같았다.

A. Buying A House :: http://codeforces.com/contest/796/problem/A

매우 쉬운 문제이다.

남자가 여자 집 근처에 살기위해 집을 사려하는데 여자와 최대한 가까이 살고싶고, 그리고 자신이 가진 돈 이하의 집을 사야한다.

이때 어느 집을 사야하나?

Examples

input

5 1 20
0 27 32 21 19

output

40

input

7 3 50
62 0 0 0 99 33 22

output

30

input

10 5 100
1 0 1 0 0 0 0 0 1 1

output

20

1번 예제는 여자가 1번 집에살고 남자의 수중에는 20의 돈이 있다.

이때 27, 32, 21은 모두 비싸서 못사니 19를 사야한다. 따라서 40

2번 예제는 여자가 3번 집에살고 남자의 수중에는 50이 있다.

이때 33, 22를 살 수 있으니 33을 사면 된다. 따라서 30

3번 예제는 여자가 5번 집에살고 남자의 수중에는 100이있다.

아무 집이나 다 살 수 있으니 5번가 가장 가까운 집을 사면된다. 따라서 3번 집을 사게 되고 거리는 20이 된다.

시간 복잡도는 O(N)이다.

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n, m, k;
    int house[102];
 
    scanf("%d %d %d", &n, &m, &k);
 
    for (int i = 1; i <= n; i++)
        scanf("%d", &house[i]);
 
    int MIN = 99999;
 
    for (int man = 1; man <= n; man++)
    {
        if (house[man] == 0)
            continue;
 
        if (k < house[man])
            continue;
 
        MIN = min(MIN, abs(man - m));
    }
 
    printf("%d", (MIN) * 10);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

B번 문제는 다음과 같다.

B. Find The Bone :: http://codeforces.com/contest/796/problem/B

야바위를 하는데 개 뼈다귀가 어디있는지 알아보라는 문제이다.

인풋의 2번째 줄에는 테이블에 구멍이있다고 말해주고 있다.

2번째 줄에 해당하는 위치로 뼈가 가면 뼈는 테이블 밑으로 떨어지게되어 

그 후로 어떻게 야바위를 하건간에 컵에없고 테이블 아래위치에 있게 된다.

Examples

input

7 3 4
3 4 6
1 2
2 5
5 7
7 1

output

1

input

5 1 2
2
1 2
2 4

output

2

1번 예제의 경우 3, 4, 6에 구멍이 있지만, 컵은 3, 4, 6을 지나지 않으므로 답은 야바위 결과인 1이 된다.

2번 예제의 경우 2에 구멍이 있기에 1 2를 하는 순간 2에 뼈다귀가 들어가면서 테이블아래로 떨어진다.

따라서 답은 2이다.

문제 조건만 잘 따라오면 O(N)에 해결 가능한 문제이다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int hole[1000002];
int cup[1000002];
int main()
{
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
 
    cup[1] = 1;
    for (int i = 1; i <= m; i++)
    {
        int val;
        scanf("%d", &val);
        hole[val] = 1;
    }
 
    if (hole[1] == 1)
    {
        printf("1");
        return 0;
    }
 
    for (int i = 0; i < k; i++)
    {
        int first, second;
        scanf("%d %d", &first, &second);
 
        if (cup[first] == 1)
        {
            cup[first] = 0;
            cup[second] = 1;
        }
        else if (cup[second] == 1)
        {
            cup[second] = 0;
            cup[first] = 1;
        }
 
        if (cup[second] == 1 && hole[second] == 1)
        {
            printf("%d", second);
            return 0;
        }
 
        else if (cup[first] == 1 && hole[first] == 1)
        {
            printf("%d", first);
            return 0;
        }
    }
 
    for (int i = 0; i <= n; i++)
        if (cup[i] == 1)
            printf("%d", i);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

C번과 D번은 문제를 나름대로 접근했다 생각했지만, 결과적으로 정답 코드를 보고 나니 틀렸다는 것을 느꼈다.

C번은 트리로 만들어서 적절하게 DFS를 돌리면 해결 될 것 같았다고 생각했고,

정답을 푼 사람들은, RMQ, map STL, DP 등등으로 푸신 분들이 많았다.

D번 문제는 최소 스패팅 트리 응용 문제인 것 같아 경찰서를 분기점으로 prim 알고리즘을 돌리면 어떨까 생각했지만,

이것도 DP, 다익스트라 등등의 다양한 방법이 존재했다.

이번 문제가 C부터 확 어려워진 감이있기도하지만 다음 부터는 안정적인 문제에서 실수없이 

점수를 많이 받으며 어려운 문제도 도전 해 봐야 겠다.