[python]25682번 체스판 다시 칠하기 2, 2000*2000제한 사항 확인

첫번째 시도..

누적합을 떠올리지 못하고 정직하게 브루트포스로 값 하나하나 세주었다.

시간초과가 떠서 실패했다.

 

누적합 적용

틀렸습니다가 뜨기에 누적합을 다시 확인해보았다.

IMOS알고리즘에 의하면 가로,세로로 누적합을 적용시키면 오른쪽 아래 값이 2차원배열의 총 합이 된다.

이때 체스판에서는 총 합이 아닌 부분합이 필요하기에 해당 범위 외에 값을 빼주었다.

아래 그림으로 설명해보았다.

 

큰 사각형에서 빨간색 직사각형의 값을 구하고 싶다.

그러면 빨간색 영역 외, 파란색&노란색 부분을 전체 값에서 빼면 된다.

그러나 그러면 보라색 부분이 중복으로 빼지게 된다.

따라서 보라색 부분의 총합을 다시 더해주어 빨간색 부분 합값을 구할 수 있게 된다!!

import sys
input = sys.stdin.readline
rw,clmn, k = map(int,input().split())
stg = []
bstg = [[0 for i in range(clmn)]for j in range(rw)]  #왼쪽 위가 검정일 때
wstg = [[0 for i in range(clmn)]for j in range(rw)]  #오른쪽 위가 하양일 때
for i in range(rw):
    stg.append(list(input().strip()))
for i in range(rw):           #누적합을 시키기 위해 더할 부분 표시
    for j in range(clmn):
        if i%2==0 and j%2==0 and stg[i][j]=="W":
            bstg[i][j]+=1
        elif i%2==1 and j%2==0 and stg[i][j]=="B":
            bstg[i][j]+=1
        elif i%2==1 and j%2==1 and stg[i][j]=="W":
            bstg[i][j]+=1
        elif i%2==0 and j%2==1 and stg[i][j]=="B":
            bstg[i][j]+=1
        if i%2==0 and j%2==0 and stg[i][j]=="B":
            wstg[i][j]+=1
        elif i%2==1 and j%2==0 and stg[i][j]=="W":
            wstg[i][j]+=1
        elif i%2==1 and j%2==1 and stg[i][j]=="B":
            wstg[i][j]+=1
        elif i%2==0 and j%2==1 and stg[i][j]=="W":
            wstg[i][j]+=1
for i in range(rw):              #누적합 적용 가로 부분
    for j in range(1,clmn):
        bstg[i][j]+=bstg[i][j-1]
        wstg[i][j]+=wstg[i][j-1]
for i in range(1,rw):            #누적합 적용 세로 부분
    for j in range(clmn):
        bstg[i][j]+=bstg[i-1][j]
        wstg[i][j]+=wstg[i-1][j]
rst = 10**5
for i in range(k-1,rw):          #K크기의 사각형으로 최솟값 찾기
    for j in range(k-1,clmn):
        if i-k>=0:
            if j-k>=0:
                rst=min(rst,bstg[i][j]-bstg[i-k][j]-bstg[i][j-k]+bstg[i-k][j-k],wstg[i][j]-wstg[i][j-k]-wstg[i-k][j]+wstg[i-k][j-k])
            else:
                rst=min(rst,bstg[i][j]-bstg[i-k][j],wstg[i][j]-wstg[i-k][j])
        else:
            if j-k>=0:            
                rst=min(rst,bstg[i][j]-bstg[i][j-k],wstg[i][j]-wstg[i][j-k])
            else:
                rst=min(rst,bstg[i][j],wstg[i][j])
print(rst)

이때 위 코드를 제출하면 틀렸습니다.가 뜬다.

왜냐하면 처음 최솟값을 설정하기 위해 rst변수에 나름대로 큰 값(10**5)을 부여 했다고 생각해서이다.

그러나!!  체스판의 크기는 2000*2000이기에 칸이 최대 4*10**6개이다. 따라서 10**5보다 큰 값이 최솟값이 될 수 있어서 그런것이었다.

rst = 10**10 #더 넉넉하게 잡았다

 rst값을 고치면 정답이 되었다

 

다른 엄청난 고수분(snnjjang)의 풀이

def check(color):
    dp = [[0] * (M+1) for _ in range(N+1)]     #조건식 안세우게끔 여유공간 줘버리기!!!

    for i in range(N):
        for j in range(M):
            if (i+j) % 2 == 0:  #무친 수식으로 단번에 값 설정
                v = board[i][j] != color
            else:
                v = board[i][j] == color

            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + v   #가로,세로 두번 하지 않고 한번에 2차원 누적합 하는법!!, 똑같이 중복값인 왼쪽 위 값만 빼주면 됨!!

    count = N * M + 1
    for i in range(1, N-K+2):
        for j in range(1, M-K+2):
            count = min(count, 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 count

N, M, K = map(int, input().split())
board = [list(input()) for _ in range(N)]

print(min(check("B"), check("W")))