[SWEA 4613] 러시아 국기 같은 깃발 (python)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQl9TIK8qoDFAXj&categoryId=AWQl9TIK8qoDFAXj&categoryType=CODE&problemTitle=4613&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

요즘 dp문제를 많이 풀었더니 뇌가 일을 안한다..
모든 문제가 dp로 보입니다..

 

 

🔥 작성 코드 (🌪️56,928kb 127ms)

T = int(input())

for test_case in range(1, T+1):
    N, M = map(int, input().split())
    arr = [input() for _ in range(N)]

    dp = [[0, 0, 0] for _ in range(N)]
    for i in range(N):
        dp[i][0] = M - arr[i].count('W')
        dp[i][1] = M - arr[i].count('B')
        dp[i][2] = M - arr[i].count('R')

    result = dp[0][0] + dp[N-1][2]

    dp[1][2] = N*M
    dp[N-2][0] = N*M
    for i in range(2, N-1):
        dp[i][0] += dp[i-1][0]
        dp[i][1] += min(dp[i-1][0], dp[i-1][1])
        dp[i][2] += min(dp[i-1][1], dp[i-1][2])

    result += min(dp[N-2])

    print(f'#{test_case} {result}')

 

⭕ 해설

1.  입력받은 문자열을 2차원 배열인 dp에 옮깁니다.
   • dp는 3개의 요소를 가진 리스트 N개의 집합입니다.
   • 국기의 인덱스는 0부터 N-1까지입니다.
   • dp는 W, B, R순으로 각 행을 이것으로 채울 때 변경해야 할 요소의 개수입니다.
     • ex) 'BWRWB' 는 dp에 [3, 3, 4]와 같이 저장됩니다.
2. dp를 돌며 값을 저장하기 전에 result를 셋팅합니다.
   • dp의 앞에서 두 번째 줄과 뒤에서 두 번째 줄은 각각 빨강, 하양으로 칠 할 수 없습니다.
     • 따라서 앞에서 두 번째 줄의 세번째 값은 모든 칸을 채울 수 있는 최댓값인 N*M으로 설정
     • 똑같이뒤에서 두 번째 줄의 첫번째 값은 모든 칸을 채울 수 있는 최댓값인 N*M으로 설정
   • 만약 N=3 이라면 dp[2]의 값은 [3*M, 행에 있는 W, R 개수의 합,3*M] 이 됩니다.
3. 두 번째 줄부터 뒤에서 두번째 줄까지 돌면서 dp를 채워줍니다.
   • 하얀색으로 색칠하려면 이전 행이 하얀색이어야 가능합니다.
   • 파란색으로 색칠하려면 이전 행이 하얀색 또는 파란색일 경우에 가능합니다.
   • 빨간색으로 색칠하려면 이전 행이 파란색 또는 빨간색일 경우에 가능합니다.
4. 이 경우를 비교해가며 마지막 N-2행까지 최솟값을 저장합니다.
5. 첫 행과 마지막 행을 칠하는 경우는 미리 결과값에 저장했으므로 dp[N-2]의 최솟값을 더해줍니다.

 

 

---

DP 관련 문제 더보기

 

2022.02.16 - [Algorithm😵‍💫/BAEKJOON] - [백준 BOJ] 9465 스티커 (python)

[백준 BOJ] 9465 스티커 (python)

 

2022.02.16 - [Algorithm😵‍💫/BAEKJOON] - [백준 BOJ] 1149 RGB거리 (python)

[백준 BOJ] 1149 RGB거리 (python)

 

2022.02.15 - [Algorithm😵‍💫/BAEKJOON] - [백준 BOJ] 2225 합분해 (python)

[백준 BOJ] 2225 합분해 (python)