[백준 9465] 스티커(Python)

문제

유형 

dp 

 

아이디어

이 문제를 읽고 처음에는 완전탐색을 떠올렸다.

하지만 dfs/bfs를 이용하면 선택하지 않은(이웃하지 않은) 스티커를 매 column마다 반드시 하나는 선택하기 때문에 

한 column에서 스티커가 하나도 선택되지 않는 경우는 고려할 수 없을 것이라는 생각에 다른 아이디어를 생각했다.

 

-> dp 아이디어 !

dp 테이블을 이용해 해당 칸까지 얻을 수 있는 점수를 매 칸마다 계산한다면 위의 한계점을 극복할 수 있을 것이라 생각했다.

해당 칸의 스티커가 선택된 경우, 이웃 column의 스티커가 선택될 수 있거나 선택되지 않을 수 있다는 점을 주의하자!

이웃 column의 스티커가 선택되지 않은 경우, 그 이전 column의 0 또는 1행의 스티커가 선택되는 경우가 존재한다 

 

<dp 로직 정리>

• dp[i][j] : 해당 칸의 스티커를 선택할 때 얻을 수 있는 최대 점수 (각 칸에 놓인 스티커의 점수로 초기화 됨
• dp[i][j] = dp[i][j] + max(dp[1-i][j-1], dp[i][j-2], board[1-i][j-2]) 
  • dp 테이블 갱신 -> (1) 이전 column의 스티커가 선택되는 경우( dp[1-i][j-1] )
                                 (2) 이전 column의 스티커가 선택되지 않은 경우, ( dp[i][j-2], board[1-i][j-2] )
                                       - 그 이전 column의 0 행의 스티커가 선택되는 경우 
                                       - 그 이전 column의 1행의 스티커가 선택되는 경우 
  • 이때, 행 인덱스를 1-i 로 표현함,
    행이 0, 1 인덱스만 존재하기 때문에 해당 스티커의 행이 아닌 다른 행을 뜻한다 

구현 코드 

T = int(input())
for _ in range(T):
    n = int(input())
    board = [] #(2, n): 해당위치까지 가능한 점수의 최대
    for _ in range(2):
        board.append(list(map(int, input().split())))

    if n == 1:
        print(max(board[0][0], board[1][0]))
        continue

    board[0][1] += board[1][0]
    board[1][1] += board[0][0]
    if n == 2:
        print(max(board[0][1], board[1][1]))
        continue

    for j in range(2, n):
        for i in range(2):
            board[i][j] += max(board[1-i][j-1], board[i][j-2], board[1-i][j-2]) #옆컬럼을 선택한 경우, 선택하지 않은 경우

    print(max(board[0][n-1], board[1][n-1], board[0][n-2], board[1][n-2]))