9461 파도반 수열
DP문제의 핵심은 점화식 만들기인 것 같고 그걸 얼마나 그럴싸하게 만들어내느냐가 관건인듯하다. 이 문제는 점화식을 만들기 쉬워서 풀 수 있었다. 단순히 f(n) = f(n-1) + f(n-5)만 찾아내면 풀 수 있었는데 f(n)이 정말 여러 형태로 나올 수 있었기 때문에 어렵지않게 해결할 수 있었다.
n = int(input())
tri = [0] * 101 # 여기 100으로 한거때문에 런타임에러 ....
tri[1] = 1
tri[2] = 1
tri[3] = 1
tri[4] = 2
tri[5] = 2
for i in range(n):
t = int(input())
for j in range(6, t+1):
if tri[j] == 0:
tri[j] = tri[j-1] + tri[j-5]
else:
continue
print(tri[t])1912 연속합
시간초과 때문에 어려웠다. 처음에 푼 풀이는 다음과 같았다.
# 처음에 푼 풀이
import sys
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().strip().split()))
chklst = []
# 10만 * 10만
# for문을 최대한 적게 사용하는 방향으로 / sum이나 append보단 for문이 2개인게 문제
for i in range(n):
for j in range(i+1, n+1):
chklst.append(sum(nums[i:j]))
print(max(chklst))1번째부터 2번째까지, 3번째까지, ... n번째까지 더한 값을 저장하고 다시 2번째부터 3번째까지, 4번째까지 .... n번째까지 합들을 저장해서 가능한 모든 경우의 수를 다 저장해서 그 안의 max값을 추출하려고 했는데, 범위가 넓다보니 for문 2개를 쓴 탓에 시간초과가 났던 것 같다. 같이 공부하는 사람의 피드백을 들었을 때, 2중 for문이 정말 시간을 많이 잡아먹으므로 지양하는 것이 좋다고 했다. 그래서 다음 풀이는 for문이 1개이다.
# 정답풀이
import sys
n = int(input())
nums = list(map(int, sys.stdin.readline().strip().split()))
# 핵심 - 내가 너랑 힘을 합치는게 이득이냐 아니냐를 따지는것
for i in range(1, n):
nums[i] = max(nums[i], nums[i-1] + nums[i])
print(max(nums))이 풀이의 핵심은 "내가 너랑 힘을 합치는게 이득인지 아닌지 따진다" 였다. 여기서 말하는 "내가"는 뒤에 있는 숫자들을 지칭한다. for i in range(1, n): nums[i] = max(nums[i], nums[i-1] + nums[i]) 이 부분을 보자. nums에 새롭게 값들을 할당하는데 이 값들은 max값들이다. 만약 뒤에 있는 내가(nums[i]) 앞에 있는 nums[i-1]과 합쳤을때 힘이 세진다면 max를 통해 새롭게 nums[i]값이 바뀌고, 아니라면 그대로 두게 된다. 이 과정을 반복하면 가장 힘이 센(값이 큰) 값들이 계속해서 nums에 할당되고 그 안에서 최댓값을 찾으면 된다.
ex. nums에 10 -4 3 1 5 6 -35 12 21 -1 이 있다고 하자. 값이 새롭게 할당되는 과정은 다음과 같다.
10 -4 3 1 5 6 -35 12 21 -1
10 6 3 1 5 6 -35 12 21 -1
10 6 9 1 5 6 -35 12 21 -1
10 6 9 10 5 6 -35 12 21 -1
10 6 9 10 15 6 -35 12 21 -1
10 6 9 10 15 21 -35 12 21 -1
10 6 9 10 15 21 -14 12 21 -1 -> 12 기준에서 볼때 -14랑 힘을 합치는게 손해이므로 합치지 않는다.
10 6 9 10 15 21 -14 12 21 -1
10 6 9 10 15 21 -14 12 33 -1
10 6 9 10 15 21 -14 12 33 32
=>> 따라서 max는 33
