백준 #1633 최고의 팀 만들기

코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline


arr = []
while True:
    try:
        a, b = map(int, input().split())
        arr.append((a, b))
    except:
        break

n = len(arr)
dp = [[[0 for _ in range(16)] for _ in range(16)] for _ in range(n + 1)]

for i in range(n):
    for w in range(16):
        for b in range(16):
            if w + b > i:
                continue
            if w < 15:  # 백으로 플레이
                dp[i + 1][w + 1][b] = max(dp[i + 1][w + 1][b], dp[i][w][b] + arr[i][0])
            if b < 15:  # 흑으로 플레이
                dp[i + 1][w][b + 1] = max(dp[i + 1][w][b + 1], dp[i][w][b] + arr[i][1])
            # 포함 안시키기
            dp[i + 1][w][b] = max(dp[i + 1][w][b], dp[i][w][b])

print(dp[n][15][15])

수정 코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline


arr = []
while True:
    try:
        a, b = map(int, input().split())
        arr.append((a, b))
    except:
        break

n = len(arr)
dp = [[[0 for _ in range(16)] for _ in range(16)] for _ in range(n + 1)]

for i in range(1, n + 1):
    for w in range(16):
        for b in range(16):
            if w + b >= i:  
                continue
            if w < 15:  # 백으로 플레이
                dp[i][w + 1][b] = max(dp[i][w + 1][b], dp[i - 1][w][b] + arr[i - 1][0])
            if b < 15:  # 흑으로 플레이
                dp[i][w][b + 1] = max(dp[i][w][b + 1], dp[i - 1][w][b] + arr[i - 1][1])
            # 포함 안시키기
            dp[i][w][b] = max(dp[i][w][b], dp[i - 1][w][b])

print(dp[n][15][15])

풀이

dp문제는 항상 dp배열을 어떤식으로 만들어야 할지가 고민이다 ㅠ

결국 구글의 힘을 빌려 아이디어를 빌려왔다 흑흑

dp[i][w][b]를 i번째 사람까지 갔을 때 백팀이 w명, 흑팀이 b명 포함 되어있을 때의 최고 점수로 설정했다

w 와 b의 최대값은 15이므로 (n + 1) * 16 * 16 모양의 dp 배열을 만들어 주었다

이후에는 3중 for문을 돌면서 i번째 선수가 백팀, 흑팀 그리고 무소속일 경우 3가지에 대해 max값을 갱신해주었다

풀고나면 별게 아닌데 아이디어 잡는게 항상 관건이다..ㅜㅡㅜ

---

오늘 팀원들과 코드리뷰를 했는데 내가 이 문제를 맡았다.

사실 저번에 풀 때도 긴가민가하긴 했는데 역시 설명을 하는 도중에 막혔다!!!

끝나고 다시 n의 범위를 줄여서 분석해보았다.

먼저 고친 부분은 i의 범위이다. 1부터 시작을 하는 것으로 고쳤고 dp를 갱신하는 과정에서 arr 부분 index를 수정해주었다.

이렇게 한 이유는 dp[i][w][b]를 i번째 사람까지 갔을 때 백팀이 w명, 흑팀이 b명 포함 되어있을 때의 최고 점수로 설정했는데 i를 0부터 시작하면 dp를 갱신할 때 dp[i + 1] = ~~ 식으로 해줘야해서 직관성이 떨어지는 것 같아서이다.

또한 w + b > i 를 w + b >= i로 고쳤다.

앞처럼 풀어도 맞았습니다가 뜨긴하는데 더 정확하게 풀면 등호가 들어가야한다.

현재 i번째 사람의 차례인데 백과 흑을 합쳐서 i와 같다는건 이미 i번째 사람이 백 또는 흑에 포함되어 있다는 뜻이기 때문이다.

코드리뷰를 하면서 한정님께서

$dp[i][w][b] = max(dp[i][w][b], dp[i - 1][w][b])$ 이 부분을

$dp[i][w][b] = dp[i - 1][w][b]$로 해도 되지 않냐고 물어보셨는데 나도 얼핏보기엔 상관이 없어보였다!(아직 내가 푼 방식에 대한 이해가 부족해서 ㅠㅠ)

하지만 n의 범위를 줄여보면서 디버깅을 하며 손으로 써내려가 보았는데 max가 없으면 위에서 갱신된 dp값을 그냥 무시해버리기 때문에 최대값으로 갱신이 안되는 것을 확인할 수 있었다.

위 그림에서 보면 왼쪽이 max를 쓴 것이고 오른쪽이 안쓴 것인데 i = 2 부분에서 50이여야하는 부분이 그냥 3으로 되어버리는 것을 확인할 수 있다.

또한 위에서 등호를 붙임으로써 빨간색 부분은 무조건 0이여야하는데 잘 나오는 것을 확인 할 수 있었다.

오늘 코드리뷰를 하면서 내가 많이 부족하다는 것을 느꼈다.

구글링을 해서 아이디어를 빌려왔다 해도 그냥 맞았습니다가 뜨니깐 아 이렇게 풀면 대충 되는군 하고 홱하고 넘어간 내 자신이 부끄럽다.

오늘부터는 한 문제를 풀더라도 다음에 다시 풀더라도 맞출 수 있도록 완전히 내 것으로 만들면서 풀 것이다!!