백준 16194 카드 구매하기 2

카드 구매하기 1과 비슷해서

간단하게 될거라 생각했는데 쉽지않다

 

바텀업 방식으로 짜는게 생각하기는 어렵지만 더 효율적이고 재귀제한 없으니까 이게 더 맞는것 같아서 힘들지만 바텀업으로 짜는 연습도 하기로 했다

 

import sys

n = int(sys.stdin.readline().rstrip())
p=[]
val=[]
p.append(0)
val.append(0)
for i in map(int,sys.stdin.readline().rstrip().split()):
    p.append(i)
    val.append(0)

val[1]=p[1]

for i in range(2,n+1):
    val[i]=min(p[i],val[i-1]+val[1])

print(val[n])

그래서 이렇게 작성했는데 역시 예제 케이스에서 통과하지 못하는 부분이 생긴다

 

그냥 단순하게 해당 카드를 고르기까지의 최저가격을 저장해서 거기에 p1을 더한값을 비교하면 될거라 생각했는데

이런 케이스에 정상작동하지 못한다

 

그래서 두 숫자를 골라서 합이 n이 되어야 한다는 걸 이용해서 풀어야겠다고 생각을 고쳤다

결국 최종적으로는 저번 코드와 비슷한 동작이 이루어져야한다

 

다만 이걸 어떻게 바텀업으로 작성하냐가 문제다

import sys

n = int(sys.stdin.readline().rstrip())
p=[]
val=[]
p.append(0)
val.append(0)
for i in map(int,sys.stdin.readline().rstrip().split()):
    p.append(i)
    val.append(i)

for i in range(1,n+1):
    for j in range(1,n+1):
        if i+j>n:
            break
        val[i+j]=min(val[i+j],val[i]+val[j])

print(val[n])

완성된 코드

속도도 엄청 느린것도 아니다

다만 이번에도 마찬가지로 나보다 2배더 빠른 풀이가 존재하는 모양이다