레이팅 미적용"가위바위보" 게임은 아마 들어 보았을 것이다. 소들은 이와 비슷한 "발굽 가위 보(Hoof, Paper, Scissors)"라는 게임을 즐겨 한다.
"발굽 가위 보"의 규칙은 간단하다. 두 소가 맞붙는다. 둘은 셋을 센 다음, 동시에 발굽, 종이(보), 가위 중 하나를 나타내는 동작을 취한다. 발굽은 가위를 이기고(발굽은 가위를 부술 수 있으므로), 가위는 종이를 이기고(가위는 종이를 자를 수 있으므로), 종이는 발굽을 이긴다(발굽이 종이에 베일 수 있으므로). 예를 들어 첫 번째 소가 "발굽" 동작을 하고 두 번째 소가 "종이" 동작을 하면 두 번째 소가 이긴다. 물론 두 소가 같은 동작을 하면 비길 수도 있다.
농부 존은 자신의 소 두 마리가 "발굽 가위 보"를 \(N\)판(\(1 \leq N \leq 100\)) 연달아 하는 것을 흥미롭게 지켜본다. 안타깝게도 소들이 세 가지 서로 다른 동작을 한다는 것은 알 수 있지만, 어떤 것이 "발굽"이고 어떤 것이 "종이"이며 어떤 것이 "가위"인지는 구분하지 못한다(훈련되지 않은 농부 존의 눈에는 모두 "발굽"의 변형처럼 보인다...).
세 동작의 의미를 모르는 농부 존은 동작들에 1, 2, 3이라는 번호를 붙였다. 동작 1이 "발굽"일 수도 있고 "종이"일 수도 있다. 그 의미는 그에게 분명하지 않다. \(N\)판 전체에 걸쳐 두 소가 취한 동작이 주어질 때, 번호와 동작을 적절히 대응시켰을 때 첫 번째 소가 이겼을 수 있는 판 수의 최댓값을 구해 농부 존을 도와주자.
문제 출제: 브라이언 딘(Brian Dean)
문제 출제: 브라이언 딘(Brian Dean)
입력 파일의 첫째 줄에 \(N\)이 주어진다.
나머지 \(N\)개의 줄에는 각 판을 농부 존의 관점에서 설명하는 두 정수(각각 1, 2, 3 중 하나)가 주어진다.
두 소 중 첫 번째 소가 이겼을 수 있는 판 수의 최댓값을 출력한다.
hps.in · 출력을 쓸 파일 hps.out5
1 2
2 2
1 3
1 1
3 22One solution (of several) for this sample case is to have 1 represent
"scissors", 2 represent "hoof", and 3 represent "paper". This assignment gives
2 victories to the first cow ("1 3" and "3 2"). No other assignment leads to
more victories.
riseoj 작성
출처 올림피아드 > USACO > 2016-2017 > January > Bronze