[Python] 백준 2156. 포도주 시식

www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

DP문제. 점화식은 잘 구했는데, 점화식에 맞춰서 arr를 생성하는 과정에 또 시간소모가 심했다.

table[i] = i번째 위치에서 마실 수 있는 최댓값이라고 정의하면

• i-1번째와 i-2번째 둘 다 마신 경우 = i번째 위치를 마실 수 없으므로 table[i-1]
• i-1번째를 마시지 않은 경우 = table[i-2] + arr[i]
• i-2번째를 마시지 않은 경우 = table[i-3] + arr[i-1] + arr[i]

따라서 반복문을 순회할 때, i는 최소 3부터 시작해서 n만큼 순회해야 한다. 한다. table[i-3]이 존재해야 하기 때문.

그렇다는 건, 최초로 포도주 배열을 생성할 때, 앞부분 세 자리는 비어 있어야 한다는 뜻이다.

 

 

	import sys
	n = int(sys.stdin.readline())
	# table[위치] = 이 위치까지 왔을 때 마실 수 있는 최댓값.
	# i-1, i-2 둘 다 마신 경우. = table[i-1]
	# i-1잔을 마시지 않는 경우 = table[i-2] + arr[i]
	# i-2잔을 마시지 않은 경우 = table[i-3] + arr[i-1] + arr[i]
	arr = [0,0,0]
	for i in range(n):
	arr.append(int(sys.stdin.readline()))
	table = [0 for _ in range(len(arr))]
	for i in range(3, n+3):
	table[i] = max(table[i-1], table[i-2] + arr[i], table[i-3] + arr[i-1]+arr[i])
	answer = table[-1]
	print(answer)

view raw [백준] 포도주 시식.py hosted with ❤ by GitHub