[백준OJ] 17027번 Shell Game

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

17027번: Shell Game

---

 

-풀이-

간단한 야바위 게임이다. N개의 a , b , g 를 입력받은 뒤, 진주가 맨 처음에 1번에 있었을 떄, 주인공이 맞추는 횟수, 2번에 있었을때, 3번에 있었을때를 각각 구해서 맞춘 횟수의 최댓값을 구해주면 된다.

 

a 쉘과 b쉘을 스왑을 할때, 만약 진주가 있는 위치가 현재 a라고 한다면, b로 바뀌게 되고, b에 위치한다면 a로 바뀌게 된다. 두개의 쉘에 포함이 되지않으면 바꾸지않은것이므로, 가만히 있으면된다.

그런 뒤, g를 통해 주인공이 진주의 위치를 맞췄는지 못맞췄는지 판별하면 되고, N개의 스와핑이 끝나면, 최댓값을 갱신해주면 되는 간단한 시뮬레이션이다.

 

-시간복잡도-

O(N)

 

-코드-

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;

int arr[100][3];
int n;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
	}

	int result = 0;
	for (int k = 1; k <= 3; k++) {
		int now = k;
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			int a = arr[i][0];
			int b = arr[i][1];
			int g = arr[i][2];
			if (now == a) {
				now = b;
			}
			else if (now == b) {
				now = a;
			}
			
			if (now == g) {
				cnt++;
			}
		}
		result = max(result, cnt);
	}
	cout << result;
}