January 30, 2023

3085번: 사탕 게임

문제 요약

• N x N 크기의 C, P, Z, Y로 이루어진 배열이 주어질 때, 인접한 두 칸을 바꿔 가장 긴 연속 부분(행 또는 열)의 길이를 출력
• 3 ≤ N ≤ 50

풀이

from sys import stdin

input = stdin.readline

N = int(input())
candy_list = [list(input()) for _ in range(N)]
dx = [1, 0]
dy = [0, 1]
result = 0

def count_max_candy():
    result = 1
    row_dp = [1] * N
    col_dp = [1] * N

    for i in range(N):
        for j in range(N - 1):
            if (candy_list[i][j] == candy_list[i][j + 1]):
                row_dp[j + 1] = row_dp[j] + 1
                result = max(row_dp[j + 1], result)
            if (candy_list[j][i] == candy_list[j + 1][i]):
                col_dp[j + 1] = col_dp[j] + 1
                result = max(col_dp[j + 1], result)
        row_dp = [1] * N
        col_dp = [1] * N

    return result

for i in range(N):
    for j in range(N):
        for k in range(2):
            nx = i + dx[k]
            ny = j + dy[k]
            if (0 < nx and nx < N and 0 < ny and ny < N):
                candy_list[i][j], candy_list[nx][ny] = candy_list[nx][ny], candy_list[i][j]
                result = max(result, count_max_candy())
                candy_list[i][j], candy_list[nx][ny] = candy_list[nx][ny], candy_list[i][j]

print(result)

• N의 크기가 50에 제한되므로 브루트포스를 이용하여 모든 경우의 수를 구한다.

시간 복잡도 분석

• $O(N^4)$