[Baekjoon] 3085번 : 사탕 게임 (Python, 구현, 브루트포스)

[Baekjoon] 3085번 : 사탕 게임 (Python, 구현, 브루트포스)

 

목차

  
• 코드 링크
• Python
  • 시간 초과 - 방법 1 - 메모리 116132KB / 시간 552ms / 코드 길이 872B (PyPy3 통과)

 

 

 

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

3085번: 사탕 게임

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

시간 초과 - 방법 1 - 메모리 116132KB / 시간 552ms / 코드 길이 872B (PyPy3 통과)

 

모든 블록에 대하여 연속되는 것이 얼마나 있는지를 체크하는 check 함수와 swap을 통한 좌우, 상하의 가능성을 살핀 코드이다. 다만 시간 초과가 발생한다. 아무래도 시간복잡도가 $O(N^4)$에 해당하므로 당연할지도....

 

 

def check(t):
    res = 0
    for i in range(n):
        cnt = 1
        for j in range(1, n):
            if t[i][j-1] == t[i][j]:
                cnt += 1
            else:
                cnt = 1
            res = max(res, cnt)
        cnt = 1
        for j in range(1, n):
            if t[j-1][i] == t[j][i]:
                cnt += 1
            else:
                cnt = 1
            res = max(res, cnt)
    return res

n = int(input())
l = [list(input()) for _ in range(n)]
ans = 1

for i in range(n):
    for j in range(n):
        if j < n-1:
            l[i][j], l[i][j+1] = l[i][j+1], l[i][j]
            ans = max(ans, check(l))
            l[i][j], l[i][j+1] = l[i][j+1], l[i][j]

        if i < n-1:
            l[i][j], l[i+1][j] = l[i+1][j], l[i][j]
            ans = max(ans, check(l))
            l[i][j], l[i+1][j] = l[i+1][j], l[i][j]
print(ans)