Python3,DP
문제
입출력
입출력 예시
나의 풀이 (시도)
n = int(input())
p = list(map(int, input().split()))
dp = [0 for i in range(n+1)]
p = [0] + p
for i in range(1, n+1):
if n % i == 0:
dp[i] = n // i * p[i]
else:
dp[i] = 0
print(max(dp))답은 잘 나왔지만 점화식을 세워서 푼 게 아니었다. 틀린 문제 풀이이다.
주요 포인트
4
1 5 6 7 일 때,
dp[1]은 p[1] 값으로 1이 들어간다.
dp[2]는 dp[1] + p[1] 혹은 p[2] 중 더 큰 값이 들어가므로 5이다.
dp[3]는 dp[1] + p[2], dp[2] + p[1], p[3] 중 더 큰 값이 들어가므로 6이다.
dp[4] 는 dp[1] + p[3] , dp[2] + p[2] , dp[3] + p[1] , p[4] 중 큰 값이므로 10 이 된다.
이를 점화식으로 표현하면
dp[i], dp[i-j] + p[j]이고, 이 중 가장 큰 값을 찾아야 하므로 max 함수를 사용한다.
dp[i] = max(dp[i], dp[i-j] + p[j])
최종 코드
n = int(input())
p = list(map(int, input().split()))
dp = [0 for i in range(n+1)]
p = [0] + p
for i in range(1, n+1):
for j in range(1, i+1):
dp[i] = max(dp[i], dp[i-j] + p[j])
print(dp[n])피드백
식이 안 보였지만 그래도 혼자 해보려고 많이 노력했다. 이중 반복문이 필요한 문제였고 dp와 p의 관계를 생각해서 dp 배열에 넣는 거였다.
I mean