[백준알고리즘] 9465번: 스티커 -Python

[백준알고리즘] 9465번: 스티커 -Python

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

9465번: 스티커

테스트 케이스 중에서 첫 번째 테스트 케이스로부터 도움이 많이 됐다. 처음에는 함정에 걸릴 뻔했었다. 단순히 아래 그림같이 계산을 하려 했었는데, 계산 결과와 답은 달랐기 때문에 어디서 틀렸는지 알 수 있었다.

 

처음에는 파란색으로 이어진 결과와 빨간색으로 이어진 결과만 비교하면 될 줄 알았는데, 파란색의 결과가 250, 빨간색의 결과가 190으로 정답인 260에 맞지 않았다. 정답은 50, 50, 100, 60으로 구성된 260이었고, 그러기 위해서는 단순히 이전의 대각선을 선택하는 문제가 아님을 알았다.

 

여기서는 선택할 수 있는 경우의 수가 여러개 존재하게 된다. 위의 예시처럼 아예 하나의 column을 건너뛰는 방법이다. 선택을 할 때 굳이 두 개의 column을 건너뛸 때에는 중간에 하나를 더 선택할 수 있기 때문에 현재 선택해야 하는 column기준 하나 이전 column 선택 시의 max값과 둘 이전 column 선택 시의 max값을 비교해서 최대 값을 유지하면 된다.

 

위의 그림처럼 선택하면 되는데.. 그림을 넣는게 더 헷갈릴지는 모르겠다. 현재 5번 column에서 점수를 선택하려 할 때 4번 column을 선택했다면, 대각선 위인 20점을 선택했었을 것이기 때문에 20까지의 최대 값과 60을 더하면 된다. 하지만 4번 column을 선택하지 않았다면, 3번 column에서 100점을 선택했을 것이다. (70점을 선택했다면, 4번 column에서 20점을 고르지 않을 이유가 없기 때문에) 따라서 3번 column의 100점을 선택했을 때의 최댓값에 60을 더하면 된다. 이 두 가지 값을 비교해서 최대 값으로 갱신하면 된다.

빨간 선으로 표시한 부분도 마찬가지로 40점을 선택했다면 가능한 경우는 4번 column에서 10점을 선택했거나 3번 column에서 70점을 선택했던 것이다. 두 경우의 최대 값에 40점을 더하고, 그중 최댓값으로 갱신하면 된다.

 

마지막으로 마지막 column은 최대 점수를 구할 떄 반드시 선택되기 때문에, 마지막 column의 두 경우 중에서 누적된 점수의 최댓값을 선택하면 된다.

 

import sys

TRY = int(sys.stdin.readline().strip())

for T in range(TRY):
    N = int(sys.stdin.readline().strip())
    table = [list(map(int, sys.stdin.readline().split())) for _ in range(2)]

    if N > 1:
        table[0][1] += table[1][0]
        table[1][1] += table[0][0]
    for n in range(2, N):
        table[0][n] += max(table[1][n-1], table[1][n-2])
        table[1][n] += max(table[0][n-1], table[0][n-2])

    sys.stdout.write(str(max(table[0][-1], table[1][-1])) + "\n")

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다