사용자 도구

사이트 도구


ps:problems:boj:1018

체스판 다시 칠하기

ps
링크acmicpc.net/…
출처BOJ
문제 번호1018
문제명체스판 다시 칠하기
레벨실버 4
분류

브루트포스

시간복잡도O(NM)
인풋사이즈N<=50, M<=50
사용한 언어Python
제출기록29200KB / 92ms
최고기록56ms
해결날짜2021/10/10

풀이

  • N,M의 범위가 작고 자를 크기가 고정되어 있으므로, 그냥 모든 8*8 영역에 대해서 다시칠할 갯수를 구해보는 브루트포스 방식으로도 푸는데에는 지장이 없다. 영역 한개에 대해서 계산하는 것은 O(8*8)=O(1) 이고, 영역은 O(N*M)개가 있으므로 총 시간복잡도는 O(NM).
  • 체스판 다시 칠하기 2는 이 문제를 단순 브루트포스가 불가능하도록 확장한 문제이다.

코드

"""Solution code for "BOJ 1018. 체스판 다시 칠하기".

- Problem link: https://www.acmicpc.net/problem/1018
- Solution link: http://www.teferi.net/ps/problems/boj/1018
"""


def main():
    N, M = [int(x) for x in input().split()]
    board = [input() for _ in range(N)]
    min_count = 64
    for y in range(N - 7):
        for x in range(M - 7):
            t = 'W'
            count = 0
            for xx in range(8):
                for yy in range(8):
                    if board[y + yy][x + xx] == t:
                        count += 1
                    t = 'B' if t == 'W' else 'W'
                t = 'B' if t == 'W' else 'W'
            min_count = min(min_count, count, 64 - count)
    print(min_count)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
C C​ Q J​ S
 
ps/problems/boj/1018.txt · 마지막으로 수정됨: 2022/11/17 02:39 저자 teferi