백준 카드 뒤집기 게임 [32622] 파이썬(Python) 코드 + 해설

백준에 새롭게 추가된 한국어 문제 32622 카드 뒤집기 게임 정답 코드 및 해설입니다.

 

백준 카드 뒤집기 게임 32622 문제

 

1. 문제 소개

N개의 카드가 주어지고, 각 카드는 흰색 앞면(0) 또는 검은색 뒷면(1) 상태로 놓여있다. 우리는 선택적으로 처음 X개의 카드를 뒤집는 동작을 최대 한 번 수행하여, 뒤집은 후 카드 상태에서 연속된 같은 색상의 구간 중 가장 긴 길이를 점수로 삼는다. 카드 뒤집기 게임에서 얻을 수 있는 최대 점수를 구하는 문제다.

2. 문제 해결 방법

• 각 카드의 초기 상태(0 또는 1)가 주어진다.
• 카드의 목표 점수는 뒤집기 후 연속으로 같은 색상(0 또는 1)인 가장 긴 카드 구간의 길이이다.
• 최대 한 번, 1부터 X번 카드까지 뒤집을 수 있고, 이 때 X는 1 이상 N 이하인 정수다.
• 뒤집기를 하지 않는 경우도 고려해야 한다 (X=0으로 간주).

전략:

1. 카드 상태를 앞면(0) 또는 뒷면(1)로 나타내며, 연속해서 같은 숫자가 나오는 최대 길이를 overall_max_run으로 계산한다.
2. 1부터 N까지 각 접두사 부분 [1..i] 내의 연속된 같은 숫자의 최대 길이를 prefix_max_run_length[i]로 계산한다.
3. 1부터 N까지 각 접미사 부분 [i..N] 내의 연속된 같은 숫자의 최대 길이를 suffix_max_run_length[i]로 계산한다.
4. 연속 구간의 정보를 위해 각 위치별로 뒤에서 같은 색상으로 연속된 길이 end_run[i]와 앞에서 같은 색상으로 연속된 길이 start_run[i]를 계산한다.
5. 뒤집기 연산을 선택했을 때 가능한 최대 점수를 구한다:
   • X를 선택한 경우:
     • [1..X] 구간(뒤집힌 구간)의 최대 연속 구간 길이: prefix_max_run_length[X] (뒤집기 전 구간의 최대 구간 길이와 동일)
     • [X+1..N] 구간(뒤집히지 않은 구간)의 최대 연속 구간 길이: suffix_max_run_length[X+1] (X < N 일 때만 해당)
     • 경계 X와 X+1에서 뒤집힌 상태가 동일한 색상인지 확인하여, 만약 동일하면 경계를 넘어서는 연속 구간을 형성할 수 있으므로 end_run[X] + start_run[X+1]를 계산한다 (X < N 일 때만).
6. 각 X에 대해 가능한 최대 구간 길이의 최댓값을 찾고, 전체 답을 갱신한다.
7. X=0(뒤집지 않음)인 경우는 이미 계산된 overall_max_run과 비교하여 최종 답을 구한다.

3. 백준 카드 뒤집기 게임 32622 파이썬(Python) 정답 코드

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

if N == 1:
    print(1)
    sys.exit()

end_run = [0]*N 
start_run = [0]*N  

end_run[0] = 1
for i in range(1, N):
    if A[i] == A[i-1]:
        end_run[i] = end_run[i-1] + 1
    else:
        end_run[i] = 1
start_run[N-1] = 1
for i in range(N-2, -1, -1):
    if A[i] == A[i+1]:
        start_run[i] = start_run[i+1] + 1
    else:
        start_run[i] = 1

overall_max_run = max(end_run) 

prefix_max_run_length = [0]*(N+1)
prefix_max_run_length[1] = 1
current_run_length = 1
for i in range(2, N+1):
    if A[i-1] == A[i-2]:
        current_run_length += 1
    else:
        current_run_length = 1
    prefix_max_run_length[i] = max(prefix_max_run_length[i-1], current_run_length)


suffix_max_run_length = [0]*(N+2) 
suffix_max_run_length[N] = 1
current_run_length = 1
for i in range(N-1, 0, -1):
    if A[i-1] == A[i]:
        current_run_length += 1
    else:
        current_run_length = 1
    suffix_max_run_length[i] = max(suffix_max_run_length[i+1], current_run_length)
suffix_max_run_length[N+1] = 0

answer = overall_max_run 
for X in range(1, N+1):
    prefix_part = prefix_max_run_length[X] 
    if X < N:
        suffix_part = suffix_max_run_length[X+1] 
        bridging_run_length = 0
        if (1 - A[X-1]) == A[X]:
            bridging_run_length = end_run[X-1] + start_run[X]
        scenario_max = max(prefix_part, suffix_part, bridging_run_length)
    else:
        suffix_part = 0
        bridging_run_length = 0
        scenario_max = max(prefix_part, suffix_part, bridging_run_length)
    if scenario_max > answer:
        answer = scenario_max

print(answer)

4. 정답 코드 해설

1. N과 카드 상태 배열 A를 입력받는다.
2. end_run 배열은 각 위치에서 끝나는 동일 색상의 연속 길이를 저장한다.
3. start_run 배열은 각 위치에서 시작하는 동일 색상의 연속 길이를 저장한다.
4. 전체 카드에 대한 최대 연속 구간 길이(overall_max_run)를 계산한다.
5. prefix_max_run_length[i]는 [1..i] 구간 내의 최대 연속 구간 길이를 저장한다.
6. suffix_max_run_length[i]는 [i..N] 구간 내의 최대 연속 구간 길이를 저장한다.
7. X를 0부터 N까지 순회하며, 뒤집기 시나리오를 고려한다.
   • X=0일 때는 뒤집지 않을 때의 최대 연속 구간 길이 overall_max_run를 고려한다.
   • X가 1 이상일 때:
     • 뒤집힌 구간 [1..X] 내 최대 연속 구간 길이는 prefix_max_run_length[X].
     • 뒤집히지 않은 구간 [X+1..N] 내 최대 연속 구간 길이는 suffix_max_run_length[X+1].
     • 경계에서의 확장된 연속 구간 길이는 카드 X와 X+1의 색상에 따라 계산한다. 뒤집힌 카드 X의 새로운 색상(1 - A[X])이 카드 X+1의 색상과 동일하면, end_run[X] + start_run[X+1]로 계산한다.
   • 이 세 가지 중 최대값을 현재 시나리오의 최대 연속 구간 길이로 한다.
   • 전역 최대값(answer)을 갱신한다.
8. 계산된 answer를 출력한다.

이로써 주어진 카드 뒤집기 게임에서 얻을 수 있는 최대 점수를 효율적으로 계산한다.

5.  정답 코드 추가 설명

이 문제는 연속 구간에 대한 계산과 조건별 상태 변화를 고려해야 한다. 각 단계는 다음과 같은 이유로 수행된다:

• 연속 구간 최대 길이 계산: 연속된 카드 색상이 몇 장 있는지 계산하기 위해 end_run과 start_run 배열을 사용한다.
• 접두사/접미사 구간 최대: 카드 앞부분과 뒷부분의 연속 구간에 대한 정보를 효율적으로 얻기 위해 prefix_max_run_length와 suffix_max_run_length를 사용한다.
• 경계 이어붙이기: 뒤집기 연산 후 경계 부분에서 연속 구간이 이어질 수 있는데, 이를 위해 뒤집힌 카드 색상 상태를 확인하고, end_run와 start_run을 사용하여 이어지는 구간의 길이를 계산한다.

이러한 접근 방식을 통해 각 X 값에 대해 가능한 최대 연속 구간 길이를 O(1)에 계산할 수 있다. 전체 알고리즘은 O(N) 시간 복잡도로 동작하므로, 최대 300,000개의 카드에 대해 효율적으로 답을 구할 수 있다.

6. 백준 32622 카드 뒤집기 게임 제출 결과

백준 32622 카드 뒤집기 게임 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다.