9465 스티커

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

T = int(read())

for t in range(T):
    N = int(read())
    first_row = list(map(int, read().split()))
    second_row = list(map(int, read().split()))
    g = [first_row,second_row]
    # 핵심은 삼각형 형태로 보는 것!

    d = [[0 for _ in range(N)] for _ in range(2)]

    if N == 1 :
        print(max(g[0][0],g[1][0]))
        continue

    # 초기 값은 2번째 열까지
    d[0][0] = g[0][0]
    d[1][0] = g[1][0]
    d[0][1] = d[1][0] + g[0][1]
    d[1][1] = d[0][0] + g[1][1]
    # 첫번째 행 -> 두번째 행 순으로 읽자.
    for n in range(2,N):
        for r in range(2):
            now_row = g[r][n]
            # 3개의 칸의 maximum 값을 찾자.
            max_val = d[(r-1)%2][n-1]
            max_val = max(max(max_val,d[0][n-2]),d[1][n-2])

            d[r][n] = max_val + now_row

    first_max = max(d[0])
    second_max = max(d[1])
    result = max(first_max,second_max)

    print(result)

3. 풀이 및 생각

문제 풀이

문제를 보면, 어떤 경우에는 한 column을 아예 쓰지 않고 뛰어넘는 경우가 발생함을 알 수 있다. 그렇기 때문에 이 문제는 -1 column의 대각선 값만 보는 것이아니라, -2 column도 봐야함을 알 수 있다. 따라서 점화식은 다음과 같다. d[r][n] = max(d[(r-1)%2][n-1],d[0][n-2],d[1][n-2])

나의 생각

조금씩 조금씩 점화식을 어떻게 세워야할지 감이 잡혀가는 듯 하다!!