[Python] 백준 25682 체스판 다시 칠하기 2

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

25682번: 체스판 다시 칠하기 2

문제 해결

1018번과 같은 유형이지만 시간초과 압박이 있다.

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

1018번: 체스판 다시 칠하기

하지만 별 생각이 안나서 비슷하게 풀어 봤다.

CODE

import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
T = [list(str(input().strip())) for _ in range(n)]
target = n*m
for i in range(n-k+1):
    for j in range(m-k+1):
        index1 = 0
        index2 = 0
        for a in range(i,i+k):
            for b in range(j,j+k):
                if (a+b)%2==0:
                    if T[a][b] =="B":
                        index1 +=1
                    else:
                        index2 +=1
                else:
                    if T[a][b] =="W":
                        index1 += 1
                    else:
                        index2 += 1
        target = min(target,index1,index2)
print(target)

결론은 시간초과!

 

결국 중복적으로 일하게 되는 $m \times n$ 행렬에서 $ (i,i+k-1) \times (j, j+k-1) $ 부분행렬의 원소가 각각 "B" 인지 "W"인지 조사하는 것을 줄여야 할 것이다.

그러면 이전 정보를 가져오는 전략을 써야한다. ( ex) (i,j)를 조사할 때 (i-k,j-k) 를 사용하는 것)

이거는 dp밖에 생각이 안난다. 즉 $ n \times m $ 을 한번 조사하면서 dp를 조정한다음 dp로 정답을 찾는다는 생각을 가져야 한다.

 

CODE

import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
T = [list(str(input().rstrip())) for _ in range(n)]
def solve(color): # 1행 1열의 색이 color인 것을 조사
    dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
    for i in range(n):
        for j in range(m):
            if (i+j)%2==0:
                if T[i][j] != color: # 1행 1열의 색이 color인 것은 T[i][j]의 값이 color 가 나와야 하는데
                    value = 1  # 안나오면 패널티로 value 1을 준다.
                else:
                    value = 0 # 정상적이면 pass
            else:
                if T[i][j] == color: #1행 1열의 색이 color일때 color 반대 값이 나와야 하는데 color가 나왔으므로
                    value = 1 # 패널티로 value 1을 준다.
                else:
                    value = 0
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j] + value # 누적 패널티 적립
    target = n*m # 최대 패널티 점수 모두 1점을 얻어서 n*m일 것이다.
    for i in range(1,n-k+2): #우리는 kXk 행렬의 점수만 궁금하므로 dp를 공부했으면 다음과 같은 식은 쉬울 것이다.(누적에서 빼는 것)
        for j in range(1, m-k+2):
            target = min(target, dp[i+k-1][j+k-1] - dp[i+k-1][j-1] - dp[i-1][j+k-1] + dp[i-1][j-1])
    return target            
                
print(min(solve('B'), solve('W'))) # 적게 틀린 값을 찾으면 된다.