cyj893

저장소

백준: Gold5 - 2170, 2174, 2224

3 분 소요


오랜만이니까 쉬운 것부터 해 보자

2170: 선 긋기

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

수직선에 선을 여러 개 그어서 총 길이 구하기

#include <bits/stdc++.h>
#define P pair<int, int>
using namespace std;

P xy[1000001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        int x, y;
        cin >> x >> y;
        xy[i] = make_pair(min(x, y), max(x, y));
    }

    sort(xy, xy+n);

    long long ans = 0;
    for(int i = 0; i < n; ){
        int x = xy[i].first;
        int y = xy[i].second;

        i++;
        while( i < n && xy[i].first < y ){
            int xx = xy[i].first;
            int yy = xy[i].second;
            y = max(y, yy);
            i++;
        }
        ans += y - x;
    }
    cout << ans << endl;

}

일단 입력 받을 때 (작은 점, 큰 점)으로 저장해 주고, 정렬한다
첫 선분을 기준으로, 그 다음 선분들을 보면, y1보다 x2가 작을 경우 선분이 겹치게 되므로 갱신해 준다.

ex) 백준 예제
4
1 3
2 5
3 5
6 7

2 < 3이므로, 1 3과 2 5는 겹침 => 1 5로 업데이트
3 < 5이므로, 1 5와 3 5는 겹침 => 1 5로 업데이트
6 > 5이므로, 1 5와 6 7은 안 겹침

따라서 1 5, 6 7이므로 4 + 1 = 5

처음에 아무 생각 없이 우선순위 큐를 썼었는데, 계속 넣었다 뺐다 하면서 정렬할 필요가 없고 처음 한 번만 정렬하면 되니까 그냥 어레이 써도 된다~~ 시간이랑 메모리 다 많이 줄어 듦

2174: 로봇 시뮬레이션

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

각 로봇 처음 위치와 방향들을 입력 받고 커맨드 입력 받아서 시뮬레이션하기

#include <bits/stdc++.h>
#define P pair<int, int>
using namespace std;

int x[101];
int y[101];
int d[101];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int a, b, n, m;
    cin >> a >> b >> n >> m;

    for(int i = 1; i <= n; i++){
        char c;
        cin >> x[i] >> y[i] >> c;
        switch( c ){
        case 'E':
            d[i] = 0;
            break;
        case 'S':
            d[i] = 1;
            break;
        case 'W':
            d[i] = 2;
            break;
        case 'N':
            d[i] = 3;
            break;
        }
    }
    for(int i = 0; i < m; i++){
        int r, k;
        char c;
        cin >> r >> c >> k;

        switch( c ){
        case 'L':
            d[r] += 3 * k;
            d[r] %= 4;
            break;
        case 'R':
            d[r] += k;
            d[r] %= 4;
            break;
        case 'F':
            while( k-- ){
                x[r] += dx[d[r]];
                y[r] += dy[d[r]];
                if( x[r] <= 0 || a < x[r] || y[r] <= 0 || b < y[r] ){
                    cout << "Robot " << r << " crashes into the wall\n";
                    return 0;
                }
                for(int j = 1; j <= n; j++){
                    if( j == r ) continue;
                    if( x[j] == x[r] && y[j] == y[r] ){
                        cout << "Robot " << r << " crashes into robot " << j << '\n';
                        return 0;
                    }
                }
            }
            break;
        }
    }
    cout << "OK\n";

}

간단한 구현 문제다
F 명령일 때 굳이 f번 돌려서 그 때마다 부딪히는지 체크는 안 해도 될 거 같긴 한데, 어차피 로봇들이 100개 이하고 명령 반복 횟수도 100 이하라서 그냥 이렇게 해도 상관없다

2224: 명제 증명

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

A~Z, a~z 명제들이 주어지면 모든 도출할 수 있는 명제 구하기

#include <bits/stdc++.h>
#define P pair<char, char>

using namespace std;

int graph[53][53];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        char p, q;
        string s;
        cin >> p >> s >> q;
        graph[(p<='Z') ? (p-'A') : (p-'a'+26)][(q<='Z') ? (q-'A') : (q-'a'+26)] = 1;
    }
    for(int k = 0; k < 52; k++){
        for(int i = 0; i < 52; i++){
            for(int j = 0; j < 52; j++){
                if( graph[i][k] && graph[k][j] ) graph[i][j] = 1;
            }
        }
    }

    int cnt = 0;
    for(int i = 0; i < 52; i++){
        for(int j = 0; j < 52; j++){
            if( i != j && graph[i][j] ) cnt++;
        }
    }

    cout << cnt << '\n';
    for(int i = 0; i < 52; i++){
        for(int j = 0; j < 52; j++){
            if( i != j && graph[i][j] )
                cout << (char)((i<26) ? (i+'A') : (i-26+'a')) << " => " << (char)((j<26) ? (j+'A') : (j-26+'a')) << '\n';
        }
    }

}

플로이드 워셜로 한 번 돌려 주면 된다
A~Z를 0~25, a~z를 26~51 인덱스로 바꿔 주기 위해 (p<='Z') ? (p-'A') : (p-'a'+26)와 같이 썼다.
다시 알파벳으로 출력해줄 때는 (char)((i<26) ? (i+'A') : (i-26+'a'))

좋다

댓글남기기

참고