9465

날짜 : 2023. 10. 09

사용 언어 : python

 

문제

https://www.acmicpc.net/problem/9465

 

 

코드

import sys

t = int(sys.stdin.readline())  # 테스트케이스


def solution():
    n = int(sys.stdin.readline())
    graph = list()
    for _ in range(2):
        graph.append(list(map(int, sys.stdin.readline().split())))  # 그래프 입력
    if n == 1: return max(graph[0][0], graph[1][0])

    dp = [[0] * n for _ in range(2)]
    # 초기값 세팅
    dp[0][0], dp[1][0] = graph[0][0], graph[1][0]
    dp[0][1], dp[1][1] = graph[0][1] + graph[1][0], graph[1][1] + graph[0][0]
    if n == 2: return max(dp[0][1], dp[1][1])

    for i in range(2, n):
        # 현재 위치의 값 + (대각선 vs 기울어진 대각선)
        dp[0][i] = graph[0][i] + max(dp[1][i - 1], dp[1][i - 2])   
        dp[1][i] = graph[1][i] + max(dp[0][i - 1], dp[0][i - 2])
        # for tmp in dp:
        #     print(tmp)
        # print()
    return max(dp[0][-1], dp[1][-1])  # 가장 마지막에서 max 리턴

for _ in range(t):
    print(solution())

 

 

풀이

- 전형적인 DP 방식으로 풀이할 수 있는 문제였다.

- 스티커를 떼어내면 인접한 변을 갖는 위치의 값은 더할 수 없다.
- 그러므로 현재 위치가 (0, j)라고 가정한다면 영향을 미칠 수 있는 위치는 (1, j-1) 혹은 (1, j-2)가 된다.

* row의 인덱스가 1인 경우에는 1과 0을 각각 바꿔준다.
- 다만 해당 메모이제이션은 n의 크기가 2보다 클 때부터 가능하기 때문에 n이 각각 1, 2인 케이스는 조건문을 통해 리턴하여 오류를 피한다.

 

 

알게된 점

- 대각선으로만 접근하는 것을 인지했고 풀이 로직은 틀리지 않았지만 마지막 부분에서 n이 2일때의 케이스를 잘못적는 바람에 오답이 나왔었다.

- 해당 부분을 수정하니 바로 정답처리가 되었다.

- row 총 개수가 2개였지만 헷갈리지 않도록 조심해야겠다.

 

 

참고 사이트

-