[dp/백준] 11052번: 카드 구매하기(알고리즘 익히기)

-문제:https://www.acmicpc.net/problem/11052

-정답풀이

i개의 카드를 구매하는 방법은 (이전에 i-j개 산 것 더하기 j개가 담긴 카드팩을 사는 방법)과 그냥 i개 사는 것이 있고

이 중에 최댓값을 구하면 된다 

n=int(input())
dp=[0]*(n+1)
data=[0]+list(map(int,input().split()))
dp[1]=data[1]
for i in range(2,n+1):
    for j in range(1,i+1):
        dp[i]=max(dp[i],dp[i-j]+data[j])
print(dp[n])

-틀린풀이

처음에는 주어진 n의 약수들로만 계산헀을 때, 최댓값을 구할 수 있다고 생각했는데

마지막 예제에서 내가 생각한 방법으로는 16이 나오는데, 답은 18이다. 

 

이걸보고 약수로만 하는 것이 아니고, 더하기를 통해서 최댓값을 구해야한다고 생각했다. 

n=int(input())
data=[0]+list(map(int,input().split()))

answer=0
for i in range(1,n+1):
    if n%i ==0:
        answer=max(answer,data[i]*(n//i))
print(answer)