1660 백준 파이썬

캡틴 이다솜

문제를 고민하기에 앞서 사면체에 들어가는 대포알의 갯수를 고민해 보자.

1개, 4개, 10개, 20개... 다음은?

 

우선 밑면을 생각해 봤을때, 밑면에 추가되는 삼각형이 점점 커짐을 알 수 있다.

n이 300,000이라고 해서 300,000까지 다 구해놓기에는 우리에게 주어진 자원은 한정적이므로, 다른 방식으로 구해보자.

 

결국 우리는 n보다 같거나 많은 양의 대포가 쌓여있는 사면체가 처음 등장하기까지 구해야 한다.

그러므로, 이렇게 세울 수 있다.

n=int(input())
tri=[1,3]
d=[1,4]
idx=1
while n>d[-1]:
    idx+=1
    tri.append(tri[idx-1]+(tri[idx-1]-tri[idx-2])+1)
    d.append(d[idx-1]+tri[idx])

tri 리스트는 밑면 삼각형의 갯수를 담고 있는 리스트이다.

삼각형은 1개, 3개, 6개, 10개...로 커지므로 

현재 삼각형을 T(k)라고 하면 

T(k)=T(k-1)+(T(k-1)-T(k-2)+1)로 구할 수 있다.

 

그리고 이 밑면이 이전 사면체에 붙으면 현재 사면체가 되므로, 

현재 사면체 d(k)에 대해

d(k)=d(k-1)+T(k)라고 할 수 있다.

 

그 다음은 본격적인 동적 프로그래밍이다.

dp=[9999999 for x in range(n+1)]
dp[0]=0
dp[1]=1
for x in range(2,len(dp)):
    for std in d:
        if x-std>=0:
            dp[x]=min(dp[x],dp[x-std]+1)
print(dp[-1])

사면체 리스트 d를 반복시켜 2부터 n까지 dp값을 초기화 해준다.

 

전체코드

n=int(input())
tri=[1,3]
d=[1,4]
idx=1
while n>d[-1]:
    idx+=1
    tri.append(tri[idx-1]+(tri[idx-1]-tri[idx-2])+1)
    d.append(d[idx-1]+tri[idx])
dp=[9999999 for x in range(n+1)]
dp[0]=0
dp[1]=1
for x in range(2,len(dp)):
    for std in d:
        if x-std>=0:
            dp[x]=min(dp[x],dp[x-std]+1)
print(dp[-1])