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

문제 URL : https://www.acmicpc.net/problem/25682

 

소스코드 :

2차원 누적합 문제입니다.

정사각형이니

좌상단을 b로 잡을때와 혹은 w로 잡을때

의 보드를 이용한다면 dp가 2개가 필요할겁니다

 

소스코드:

 

n,m,k = map(int,input().split())
l =[input() for i in range(n)]
board=[[0]*(m+1) for i in range(n+1)]
board2=[[0]*(m+1) for i in range(n+1)]
for i in range(n):
    for j in range(m):
        board[i+1][j+1] = board[i][j+1]+board[i+1][j]-board[i][j]
        board2[i+1][j+1] = board2[i][j+1]+board2[i+1][j]-board2[i][j]
        if (i+j)%2 ==0 :
            if l[i][j]=='W':
                board[i+1][j+1]+=1
            else :
                board2[i+1][j+1]+=1
        else:
            if l[i][j]=='B':
                board[i+1][j+1]+=1
            else :
                board2[i+1][j+1]+=1

res = int(1e9)
for i in range(n-k+1):
    for j in range(m-k+1):
        res = min(res,board[i+k][j+k]+board[i][j]-board[i+k][j]-board[i][j+k])
        res = min(res,board2[i+k][j+k]+board2[i][j]-board2[i+k][j]-board2[i][j+k])
print(res)

 

 

 

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.