[USACO] 2022_Mar. Photoshoot [Bronze] [BOJ - 24980_G4]

📚 문제

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

N마리의 소들이 있다.

맨 앞부터 뒤집어서 Guernseys들이 짝수에 놓일 수 있는 최소 횟수를 구하는 것이다.

뒤집는 방법은 1번부터 5번까지 뒤집으면 1 2 3 4 5 -> 5 4 3 2 1이 되는 것이다.

즉, G H H G H 이면 H G H H G가 된다.

규칙성을 찾는 것이 중요하다.

1. 2가지씩 끊어서 생각한다.

2. 홀수와 짝수가 같은 경우는 결과에 영향을 주지 않으니 건너뛴다.

   ex). (G, G), (H, H)

3. 조합이 바뀌는 경우 회전한다.

   GH에서 HG로 바뀌거나 반대로 바뀌는 경우만 회전한다.

   GH에서 GH가 또 나오면 pass

위 같이 회전하면 G가 홀수에 가장 많아지던지 짝수에 가장 많아진다.

따라서 HG로 끝나는 경우 회전했으면 홀수에 가장 많은 경우이다. 따라서 이 경우에는 횟수를 1 빼서 짝수가 가장 많았던 경우로 출력한다.

앞에서부터 확인하면서 홀짝에서 짝홀로 넘어가는 구간에 회전을 한 번 해준다.

📒 코드

n = int(input())
arr = input()

prv = -1    # 이전 조합 기억
cnt = 0     # 회전하는 횟수
for i in range(0, n, 2):    # 2개 씩 확인
    if arr[i] == arr[i + 1] or prv == arr[i]:   # 2개가 같거나 이전에 나왔던 조합과 같으면 continue
        continue
    prv = arr[i]    # 다른 조합이 나오면 이전 값에 적어주고
    cnt += 1        # 회전 + 1

if prv == 'H':      # 이미 짝수가 가장 많은데 홀수가 가장 많게 뒤집어 버린 경우 -1 해준다.
    cnt -= 1
print(cnt)

🔍 결과