1018. 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

Solution

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

ans = N*M
for i in range(0,N-7):
    for j in range(0,M-7):
        sum = 0
        for b in range(i,i+8):
            for a in range(j,j+8):
                if (a+b)%2==0:
                    if board[b][a]=='B':
                        sum += 1
                else:
                    if board[b][a]=='W':
                        sum += 1
        ans = min(ans, min(sum, 64 - sum))
print(ans)

• 4중 for 문을 사용하여 풀었다.
• N, M 이 50이 이하이기 때문에 시간초과가 뜨지 않을 수 있었다.
• (흰색으로 시작하는 체스판을 만드는데 필요한 횟수 + 검은색으로 시작하는 체스판을 만드는데 필요한 회수)는 항상 64이다.
• 그래서 한 방면으로 계산하고 나중에 min을 구하면 된다.

 

Another

import sys
from itertools import accumulate as acc
input = sys.stdin.readline
n, m = map(int, input().split())
y = [[0]*(m+1)]
for i in range(n):
    ac = [0]
    ac.extend(acc([((s=='W')+i+j)%2 for j, s in enumerate(input().strip())]))
    y.append([k + j for k, j in zip(ac, y[-1])])

res = 32
for i in range(n-7):
    for j in range(m-7):
        u = y[i+8][j+8]-y[i+8][j]-y[i][j+8]+y[i][j]
        res = min(res, u, 64-u)
print(res)

• readline 을 input으로 지정하고 입력을 받는다.
• 가로 크기+1만큼 [0, 0, ..., 0] 리스트를 만든다.
• 한 줄씩 입력을 받으면서 그 때의 자표(i+j)와 'W' 여부를 더해서 2로 나눈 나머지로 나눈 것으로 2차원 리스트 y를 채운다. (extend가 아니라 append로 추가하면 [0, [1, 3, 5...]] 처럼 된다.)
• 이것은 한 행에 대해서 'W', 'B' 가 번갈아 나오기 위해서 왼쪽에서 오른쪽으로 가는데 몇 개을 뒤집어야 하는 지에 대한 횟수이다.
• 그것을 이전에 계산했던 y[-1]에 누적해서 더하고 이를 y 뒤에 추가한다.
• 결과적으로 왼쪽 맨 위에서 해당 지점까지 가는데 뒤집어야 하는 누적 개수가 2차원 리스트로 저장된다.
• 그래서 (마지막이 될 지점) - (시작이 될 지점) 을 계산해서 최종 답을 구한다.

 

sys.stdin.readline

sys.stdin.readline() 으로 입력을 받는 것이 input() 보다 더 빠르고, 여러 라인을 입력받을 때는 꼭 사용하는 게 좋다.

input = sys.stdin.readline 를 선언해서 사용해도 좋다.

 

strip()

인자로 받은 문자를 string의 왼쪽 오른쪽에서 제거한다.

인자로 받은 문자가 없다면 공백을 제거한다.

a = " hello world "
b = a.strip()   # [hello world]
c = a.lstrip()  # [hello world ]
d = a.rstrip()  # [ hello world]
                # 괄호는 공백을 보여주기 위함

 

accumulate( )

itertools 의 accumulate() 함수는 iterable한 인자를 누적하여 iterable로 리턴해준다.

for문으로 직접 작성하여 누적해서 만드는 것보다 훨씬 빠르다.

from itertools import accumulate
a = [1, 2, 3, 4, 5]
b = list(accumulate(a)) # [1, 3, 6, 10, 15]

 

extend( )

list 의 함수로 append( ) 와 비슷하면서 다르다.

append는 리스트 끝에 인자를 그대로 넣고, extend는 리스트 끝에 iterable한 모든 항목을 넣는다.

a = [1, 2, 3]
b = [4, 5]
c = [6, 7]
a.append(b) # [1, 2, 3, [4, 5]]
a.extend(c) # [1, 2, 3, [4, 5], 6, 7]

 

zip( )

두 그룹의 데이터를 묶어준다.

a = [1, 2, 3]
b = [4, 5, 6]
for c in zip(a,b):
    print(c)
    # (1, 4)
    # (2, 5)
    # (3, 6)