USACO: shell game

문제 url: http://www.usaco.org/index.php?page=viewproblem2&cpid=891

문제를 읽어보면 간단하다.
아래와 같은 게임을 코드로 simulation하는 문제이다.

다만 이 문제에선 위 게임을 조금 변형시켰다. 원래 게임 방식은 컵 아래에 놓여질 돌의 위치를 알고 진행자가 막 섞은다음에 마지막 위치의 자리를 맞추는것이다.
하지만 이 문제는 처음 돌의 위치를 가르쳐 주지 않는다.
게임 진행은 다음과 같다.
1. 총 세개의 컵이 있다. 한개의 돌을 셋중 한개 아래에 놓는다.
2. 한번에 한번씩 두 개의 컵 위치를 바꾼다. 그대로 있을순 없다.
3. 위치를 한번씩 바꾸고 player은 공의 위치를 추측한다. 이때, 공의 위치를 맞추면 1점을 준다.
4. 입력으로 모든 swap이 들어온다. 첫 번째 줄은 총 swap의 수다. 아래 각 한줄은 a, b, g로 순서대로 있는데 a와 b의 자리를 바꾼 후, g는 player가 돌의 위치를 추측한 자리이다.
ex)
3
1 2 1
3 2 1
1 3 1
5. 위와같은 상황일때 player가 얻을 수 있는 최대 점수를 출력하는것이 문제이다.

이 문제는 brute force로 풀면된다. 문제에서 number of swaps가 1 <= n <= 100, 이고 컵의 갯수도 3개이니 모든 경우의 수를 돌려보아도 300번 밖에 실행되지 않아서 time limit에 걸릴 걱정은 하지 않아도된다. Time complexity는 O(3n), 즉 O(n)이다.

이 문제는 처음에 돌이 1번째 컵에 있었을때의 점수, 2번째 컵에 있었을때의 점수, 3번째 컵에 있었을때의 점수를 다 구하고 가장 높은 점수를 프린트 하면 된다.

def get_score(initial_loc):
    global N, A, B, G
    current_loc, score = initial_loc, 0
    for i in range(N):
        if current_loc == A[i]:
            current_loc = B[i]
        elif current_loc == B[i]:
            current_loc = A[i]
        if current_loc == G[i]:
            score += 1
    return score


N = int(input())
A, B, G = [0] * 100, [0] * 100, [0] * 100
highest = 0

for i in range(N):
    A[i], B[i], G[i] = map(int, input().split())

for i in range(1, 4):
    highest = max(highest, get_score(i))

print(highest)