백준14468 소가 길을 건너간 이유 2

작성일 | In

문제 링크

  • http://icpc.me/14468

문제 출처

  • USACO 2017 February Contest Bronze 2번

풀이

주어지는 문자열에서 어떤 알파벳 x가 나오는 위치를 각각 x[0], x[1]이라고 합시다.
[ A[0], A[1] ], [ B[0], B[1] ] 구간이 겹치면 A와 B가 만난다는 것은 쉽게 알 수 있습니다.

2중 for문을 이용해 쉽게 정답을 구할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;
vector<p> v;

int main(){
	v.resize(26);
	string s; cin >> s;
	for(int i=0; i<52; i++){
		int now = s[i] - 'A';
		if(v[now].x == 0) v[now].x = i+1;
		else v[now].y = i+1;
	}

	int ans = 0;
	int n = 26;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			int s1 = v[i].x;
			int e1 = v[i].y;
			int s2 = v[j].x;
			int e2 = v[j].y;
			if(s1 < s2 && s2 < e1 && e1 < e2) ans++;
		}
	}
	cout << ans;
}