-
[백준] 9465번 문제 (스티커) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 20. 09:02
for _ in range(int(input())): t = int(input()) stickers = [[0]] for _ in range(2): stickers.append(list(map(int, input().split()))) if t < 2: print(max(stickers[1][0], stickers[2][0])) else: stickers[1][1] += stickers[2][0] stickers[2][1] += stickers[1][0] for i in range(2, t): stickers[1][i] += max(stickers[2][i - 1], stickers[2][i - 2]) stickers[2][i] += max(stickers[1][i - 1], stickers[1][i - 2]) print(max(stickers[1][t - 1], stickers[2][t - 1]))
stickers에 입력 값을 담고, 또한 dp로 활용했다.
stickers를 for문에서 반복하면서 항상 최대의 값을 저장하며 풀어야 된다.
stickers[1][1] += stickers[2][0] stickers[2][1] += stickers[1][0]
그렇기 때문에 위와 같이
stickers[1][1]에 stickers[2][0] 값을 더해주고,
stickers[2][1]에 stickers[1][0] 값을 더해준다.
위의 두 값을 미리 할당해주는 이유는 stickers[1][1]에 대하여 stickers[2][0]는 대각선상에 존재하기 때문에 동시에 두 스티커를 뗄 수가 있기 때문이다. (stickers[2][1] 경우에도 마찬가지)
그리고 for문에서는 stickers[1][i]에 대하여 max(stickers[2][i - 1], stickers[2][i - 2])를 더해주는데,(stickers[2][i] 경우에도 마찬가지)
그 이유는, stickers[2][i - 1]를 선택하면 stickers[2][i - 2]는 찢어져 있는 스티커이기 때문에 선택을 할 수 없고,
반대의 경우인 stickers[2][i - 2]를 선택한 경우에는 stickers[2][i - 1]가 찢어져 있는 스티커이기 때문에 선택을 할 수 없기 때문이다.
'Problem Solving > Baekjoon' 카테고리의 다른 글
[백준] 2011번 문제 (암호코드) 파이썬(Python) 풀이 (0) 2021.08.20 [백준] 2225번 문제 (합분해) 파이썬(Python) 풀이 (0) 2021.08.20 [백준] 9095번 문제 (1, 2, 3 더하기) 파이썬(Python) 풀이 (0) 2021.08.20 [백준] 2193번 문제 (이친수) 파이썬(Python) 풀이 (0) 2021.08.20 [백준] 2133번 문제 (타일 채우기) 파이썬(Python) 풀이 (0) 2021.08.19