USACO/Bronze

백준 14468 소가 길을 건너간 이유 2 (USACO February 2017 Bronze 2번)

ssam.. 2020. 2. 29. 22:20

문제 링크: https://www.acmicpc.net/problem/14468

 

14468번: 소가 길을 건너간 이유 2

문제 존의 농장에는 원형 목초지가 있고, 그 둘레에 길이 둘러져 있다. 존의 소는 매일 아침 이 길을 건너가 풀을 먹고 저녁에 다시 길을 건너가 헛간으로 돌아간다. 이 소들은 자신의 습관대로 매일 똑같은 방법으로 길을 건넌다. 각각의 소는 원형 길의 정해진 한 점을 지나 들어오고, 다른 점을 지나 나간다. 어떤 두 소도 길 위의 같은 점을 지나가지 않는다. 이걸 지켜본 존은 이 점들을 분석해 보기로 했다. 소는 총 26마리고, A, B, ... Z라는 이

www.acmicpc.net

A부터 Z까지 각소마다 나타난 두곳의 위치를 pos 배열에 입력받음. 

각각의 pair마다 소의 위치가 서로 엉켜있는지 확인될때마다 답을 1을 더하면 됨.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
 
int pos[200][2];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++) {
        if(pos[s[i]][0] == 0) pos[s[i]][0] = i + 1;
        else pos[s[i]][1] = i + 1;
    }
 
    int ans = 0;
    for(int i = 'A'; i <= 'Y'; i++) {
        for(int j = i + 1; j <= 'Z'; j++) {
            int a1 = pos[i][0], a2 = pos[i][1];
            int b1 = pos[j][0], b2 = pos[j][1];
            if(a1 < b1 && b1 < a2 && a2 < b2) ans++;
            else if(b1 < a1 && a1 < b2 && b2 < a2) ans++;
 
        }
    }
 
    cout << ans << '\n';
    return 0;
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

두번째 코드의 logic은 첫번째 코드와 완전히 같지만, 첫번째 코드에서 if문을 두번 사용한것을 두번째 코드에서는 한번만 사용해서 풀이함. 대신 첫번째 코드에서는 n(n-1)/2 개의 pair에 대해서 loop을 돌았는데, 두번째 코드에서는 n^2 개의 pair에 대해서 loop을 돌아야 함.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
 
int pos[200][2];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++) {
        if(pos[s[i]][0] == 0) pos[s[i]][0] = i + 1;
        else pos[s[i]][1] = i + 1;
    }
 
    int ans = 0;
    for(int i = 'A'; i <= 'Z'; i++) {
        for(int j = 'A'; j <= 'Z'; j++) {
            if(pos[i][0] < pos[j][0] && pos[j][0] < pos[i][1] && pos[i][1] < pos[j][1])
                ans++;
        }
    }
 
    cout << ans << '\n';
    return 0;
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter