스티커 ( 9465번 )

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

 

나의 풀이

from collections import deque
import sys

def _main(n_ct, n_list):
    if (n_ct == 1):
        return max(n_list[0][0], n_list[1][0])

    visit = [[True] * n_ct for _ in range(2)]
    queue = deque([(0,0), (1,0), (0,1), (1,1)])
    visit[0][0], visit[1][0], visit[0][1], visit[1][1] = n_list[0][0], n_list[1][0], n_list[0][1], n_list[1][1]
    while queue:
        x, y = queue.popleft()
        x1, y1 = (x + 1) % 2, y + 1
        x2, y2 = x, y + 2
        x3, y3 = (x + 1) % 2, y + 2
        for n_x, n_y in ((x1, y1),(x2, y2),(x3, y3)):
            if (0 <= n_x < 2) and (0 <= n_y < n_ct) and ((visit[n_x][n_y] == True) or (visit[n_x][n_y] < visit[x][y] + n_list[n_x][n_y])):
                visit[n_x][n_y] = visit[x][y] + n_list[n_x][n_y]
                queue.append((n_x, n_y))

    return max(visit[0][-1], visit[1][-1])

n = int(sys.stdin.readline())
for _ in range(n):
    n_ct = int(sys.stdin.readline())
    n_list = []
    for __ in range(2):
        n_list.append(list(map(int, sys.stdin.readline().rstrip().split())))
    print(_main(n_ct, n_list))

 

시간 복잡도

for _ in range(n): n번 수행 ( 선형 시간 복잡도 )
    n_ct = int(sys.stdin.readline())
    n_list = []
    for __ in range(2):
        n_list.append(list(map(int, sys.stdin.readline().rstrip().split())))
    print(_main(n_ct, n_list)) : bfs 탐색 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )