코드

t = int(input())

for _ in range(t):
    n = int(input())
    stickers = []

    for _ in range(2):
        stickers.append(list(map(int, input().split())))
        d = [([0] * n) for _ in range(2)]

    # 첫번째 스티커를 제거하는 경우의 DP 테이블은
    # 첫 스티커를 제거하는 점수 그대로의 값을 넣어줌
    d[0][0] = stickers[0][0]
    d[1][0] = stickers[1][0]
        
    # 1이면 인덱스 에러 발생하므로 별도로 처리
    if n == 1:
        print(max(d[0][n-1], d[1][n-1]))
        continue

    # 두번째 스티커를 제거하는 경우의 DP 테이블은
    # 첫 스티커들 기준 바로 다음에 나오는 다른 열의 값일 것이므로 
    # 아래와 같이 넣어줌
    d[0][1] = d[1][0] + stickers[0][1]
    d[1][1] = d[0][0] + stickers[1][1]
    
    for i in range(2, n):
        # i번째 스티커를 선택하는 경우
        # 그 이전까지의 경우는 
        # 다른 열의 i-1번째 스티커
        # 다른 열의 i-2번째 스티커를 선택하는 경우 이외에는 없다
        # 그 두 경우까지의 최대 점수에 선택할 i번째 스티커의 점수를 더해주면
        # i번째 스티커까지 선택한 최대 점수를 구할 수 있다
        d[0][i] = max(d[1][i-1], d[1][i-2]) + stickers[0][i]
        d[1][i] = max(d[0][i-1], d[0][i-2]) + stickers[1][i]

    # DP 테이블에 저장된 두 열의 값 중 더 큰 값이 정답
    print(max(d[0][n-1], d[1][n-1]))

DP 테이블 하나로 풀이

t = int(input())

for _ in range(t):
    n = int(input())
    d = [list(map(int, input().split())) for _ in range(2)]
    
    if n == 1:
        print(max(d[0][n-1], d[1][n-1]))
        continue
    
    d[0][1] += d[1][0]
    d[1][1] += d[0][0]
    
    for i in range(2, n):
        d[0][i] += max(d[1][i-2], d[1][i-1])
        d[1][i] += max(d[0][i-2], d[0][i-1])
        
    print(max(d[0][n-1], d[1][n-1]))

문제 해설

DP 문제.

규칙을 파악하는데 시간이 매우 많이 걸렸다…ㅠㅠ

스티커

위의 사진과 코드의 주석을 토대로 점화식의 설명을 하자면, (0,3)의 20을 선택하는 경우, 문제의 조건에서 [상 하 좌 우]의 스티커는 사용할 수 없다 했으므로 선택할 수 있는 스티커는 10, 50, 70 3개가 존재한다. 이 때, 빨간색 10의 경우 어차피 70을 선택하는 경우에 그 최댓값이 포함되어있으므로 고려할 필요없고, 50과 70 중 더 큰 경우를 선택하면 된다

따라서 점화식을 아래와 같이 세울 수 있다.

DP[0][i] = max(DP[1][i-1], DP[1][i-2])

DP[1][i] = max(DP[0][i-1], DP[0][i-2])

위의 식에서 최종적으로 max(DP[0][i], DP[1][i])

위의 점화식을 토대로 코드를 작성하면 답을 도출할 수 있다. 이 때, DP에 대한 이해도를 높이기 위하여 DP 테이블과 스티커의 점수를 받을 리스트를 별도로 구현하여 문제를 풀었는데, 구글링을 한 결과 스티커 리스트를 DP 테이블 자체로 사용하여 구현하는 것이 더 간단하다는 것을 알게 되었다. 정석으로 풀어보고 다른 방법으로도 푸는 방법을 익히도록 많은 연습을 해야겠다.

댓글남기기

참고