2018. 08. 13 백준 저지 알고리즘 정리(파이썬)

오늘은 별거 없다.

문제 9465 - 스티커

링크 - https://www.acmicpc.net/problem/9465

소스코드

import sys


num = int(sys.stdin.readline())
result = ''

for i in range(num):

    size = int(sys.stdin.readline())
    arr = [[0] * 2 for i in range(size)]

    line = sys.stdin.readline().rstrip()
    line += ' ' + sys.stdin.readline().rstrip()

    for (j, e) in enumerate(line.split()):
        arr[j % size][j // size] = int(e)

    T = [[0] * 3 for i in range(size)]
    T[0][0] = 0
    T[0][1] = arr[0][0]
    T[0][2] = arr[0][1]

    for j in range(1, size):

        T[j][0] = 0 + max(T[j-1])
        T[j][1] = 0 + max(T[j-1][0], T[j-1][2]) + arr[j][0]
        T[j][2] = 0 + max(T[j-1][0], T[j-1][1]) + arr[j][1]

    result += str(max(T[size - 1])) + '\n'

sys.stdout.write(result)

코멘트

마땅한 풀이법이 생각나지 않아서 하루종일 고민한 문제다. 다이나믹 프로그래밍을 써야한다는 힌트가 주어져도 이 정도라니 아직 한참 멀었다. 점수 자체를 3가지로 나누어서 누적해서 계산해야 한다는 점을 간과하고 있었다. '분명히 어느 시점에 갑자기 큰 점수가 나타나버리면 기존까지의 선택방식을 전부 뒤엎어야 하는 상황이 생길텐데, 그걸 어떤 수로 알지?' 를 고민했었는데, 그냥 배열을 만들어 저장하면 됐었다. 멍청이.

파이썬에서 다차원 list(배열)를 만들어야 할 때에는 [[0]*i]*j 식으로 만들면 안된다. 큰일난다. 파이썬의 list는 기본적으로 참조(reference) 방식으로 돌아가므로 위의 방식대로 만들었다간 list의 한 부분만 수정했을 뿐인데 list 전체가 바뀌는 사태가 발생할 수 있다. 이는 어제 포스팅한 내용의 문제와도 직결된다.

위의 소스 코드처럼 [[0 for i in range(3)] for j in range(4)] 이런 식으로 만드는 것이 바람직하다.