Python으로 푸는 SW Expert Academy 4613. 러시아 국기 같은 깃발

 SW Expert Academy 4613. 러시아 국기 같은 깃발

 문제는 러시아 국기 같은 깃발을 만들기 위해서 입력받은 문자열을 활용하여

새로 칠해야 하는 칸의 개수의 최솟값을 구해야 한다.

SW Expert Academy에서 푼 문제 리스트 보기

github에서 코드 보기

문제에서 제시한 조건

- 색깔의 순서는 흰색 - 파란색 - 빨간색으로 정해져 있다.

- 색깔은 반드시 한번 이상 칠해져야 한다. 그래야 러시아 국기 같은 국기가 되기 때문이다.

풀이 방법

가장 위와 아래는 반드시 흰색과 빨간색으로 칠해야 한다. 그러므로 2줄 ~ (n -1)줄 부분에 어떤 색을 칠해야 할지를 고민하면 된다.

 2줄 ~ (n -1)줄 부분에는 반드시 파란색 줄이 한 줄 이상 들어가면서도 색의 순서를 고려하여 가장 효율적으로 각 줄의 색을 선택해야 한다.

국기 정보를 받을 때, 줄마다 각각의 색을 칠하였을 때, 얼마나 많은 칸을 새로 칠해야 하는지 다음과 같은 튜플 형태로 계산해두었다.

" [ [(w를 칠하였을 때 새로 칠해야 하는 칸 수, b를 칠하였을 때 새로 칠해야 하는 칸 수, r를 칠하였을 때 새로 칠해야 하는 칸 수) ],

  [(w를 칠하였을 때 새로 칠해야 하는 칸 수, b를 칠하였을 때 새로 칠해야 하는 칸 수, r를 칠하였을 때 새로 칠해야 하는 칸 수) ],

  [(w를 칠하였을 때 새로 칠해야 하는 칸 수, b를 칠하였을 때 새로 칠해야 하는 칸 수, r를 칠하였을 때 새로 칠해야 하는 칸 수) ],]"

이제 각 줄 별로 어떤 색을 칠 할 지만 결정해면 된다.

색의 순서를 고려하여 어떤 색을 칠 할 지에 대한 경우의 수를 다음과 같이 구현하였다.

흰색과 파란색의 줄 수를 합한 값을 1 이상으로 정하고 그 나머지는 모두 빨간색이다. 

흰색과 파란색의 줄 수를 합한 값이 1 이상인 이유는 반드시 파란색이 한 줄 이상 나와야 하기 때문이다.

이미 흰색과 빨간색은 맨 위와 아래에 칠 했으므로 1~ (n-1) 부분에는 파란색만 칠 해도 상관이 없다.

이제 각 줄 별로 어떤 색을 칠 할지 결정되었다. 각 라인별로 해당 색을 칠할 때 얼마나 많은 칸을 새로 칠해야 하는지 더해보고

경우의 수 중에 가장 적은 칸을 새로 칠해야 하는 수를 출력해주면 된다.

파이썬 코드

def solve(_n, _m, map):
    # ‘W’는 흰색, ‘B’는 파란색, ‘R’은 빨간색
    # 맨 위, 맨 아래에는 이미 색이 정해져 있다.
    extra_count = _n - 2
 
    result = 99999999999
    for wnb in range(1, extra_count + 1):
        for j in range(1, wnb + 1):
            total = 0
            bc = j
            rc = extra_count - wnb
            wc = wnb - bc
 
            # 맨 위, 아래 칠할 수를 더해준다.
            wc += 1
            rc += 1
 
            # 흰색으로 wc 만큼 칠하기
            for wi in range(0, wc):
                total += map[wi][0]
 
            # 파란색으로 bc 만큼 칠하기
            for bi in range(wc, wc + bc):
                total += map[bi][1]
 
            # 빨간색으로 rc 만큼 칠하기
            for ri in range(wc+ bc,wc + bc + rc):
                total += map[ri][2]
            if result > total:
                result = total
    return result
 
if __name__ == "__main__":
    t = int(input().strip())
 
    for i1 in range(t):
        n,m = map(int, input().strip().split())
        lines = []
        for i2 in range(n):
            line = list(input().strip())
            # 각 색을 칠했을 때 새로 칠해야 하는 칸의 수를 구한다
            w = m - line.count('W')
            b = m - line.count('B')
            r = m - line.count('R')
            lines.append((w,b,r))
        count = solve(n, m, lines)
        print("#{0} {1}".format(i1+1, count))
 
 

#4613 러시아 국기 같은 깃발 #python 4613 러시아 국기 같은 깃발 #4613 러시아 국기 같은 깃발 python #삼성 4613 러시아 국기 같은 깃발 #sw expert 4613 러시아 국기 같은 깃발 

#SW Expert 러시아 국기 같은 깃발 #sw expert 러시아 국기 같은 깃발 #러시아 국기 같은 깃발 #삼성 모의 sw 역량테스트 해설 #파이썬 4613 러시아 국기 같은 깃발 #4613 러시아 국기 같은 깃발 파이썬