[Python] 4613. 러시아 국기 같은 깃발

DFS 풀이

# (이전의 색, 여태까지 칠한 칸 수, 현재 인덱스)
# 1행부터 n-2행까지 (마지막이 n-1행) 실행함
def paint(before, cnt, i):
    global answer

    # 지금까지 칠한 칸 수가 이미 answer에 들어있는 값보다 작으면 볼 필요 없다. 끊자
    if answer < cnt:
        return

    i += 1  # 인덱스 += 1

    # 만약 끝나는 곳까지 왔을 경우, 여태까지의 합이 answer보다 작다면 갱신하고 끝내기
    if i == n - 1:
        if cnt < answer:
            answer = cnt
        return

    ### 재귀로 다음 행으로 들어가기 ###
    # 만약 이 전의 라인이 흰색으로 칠해졌다면 => 다음에 칠할 수 있는 색은 흰색, 파란색
    if before == 'W':
        # 근데 마지막행의 전 행은 흰색으로 칠할 수 없다.
        if i != n-2:
            paint('W', cnt + board[i][0], i)
        paint('B', cnt + board[i][1], i)

    # 이 전의 라인이 파란색으로 칠해졌다면 => 다음 가능 색은 파란색, 흰색
    elif before == 'B':
        paint('B', cnt + board[i][1], i)
        paint('R', cnt + board[i][2], i)

    # 이 전의 라인이 빨간색으로 칠해졌다면 => 다음 가능 색은 빨간색
    elif before == 'R':
        paint('R', cnt + board[i][2], i)



tc = int(input())

for idx in range(1, tc+1):
    n, m = map(int, input().split())    # n행 m열

    board = []  # 깃발 받아올 리스트
    for _ in range(n):
        line = input()  # 줄 받아오기
        # 해당 행에 각 색으로 칠하려면 칠해야 하는 칸 넣기
        w = m - line.count('W') # 전체 칸 - 해당 색의 개수 => 칠해야 하는 칸의 개수
        b = m - line.count('B')
        r = m - line.count('R')
        board.append([w, b, r])

    # 정답 받을 변수 ㄹㅇ 큰수로 잡아준다.
    answer = 999999999999

    # 첫번째 라인은 흰색으로 칠해야하니 'W'
    # 맨 윗줄은 흰색, 맨 아랫줄은 빨강으로 해야하니, 그 개수는 넣어준다.
    # 현재 인덱스 0
    paint('W', board[0][0]+board[-1][2], 0)

    print('#{} {}'.format(idx, answer))

 

DP 풀이

tc = int(input())

for idx in range(1, tc+1):
    n, m = map(int, input().split())

    w = [0]
    b = [0]
    r = [0]
    for i in range(n):
        line = input()
        w.append(w[-1] + m - line.count('W'))
        b.append(b[-1] + m - line.count('B'))
        r.append(r[-1] + m - line.count('R'))

    paint = 9999999999999999999

    for i in range(1, n-1):
        for j in range(i+1, n):
            temp = w[i] + (b[j] - b[i]) + (r[-1] - r[j])
            if temp < paint:
                paint = temp

    print('#{} {}'.format(idx, paint))

 

(확실히 코드가 짧고 빠르다)