[파이썬] 백준 1660 : 캡틴 이다솜 (골드5)

[파이썬] 백준 1660 : 캡틴 이다솜 (골드5)

• https://www.acmicpc.net/problem/1660
  

---

풀이

방향성 생각

• 사면체 만드는데 필요한 블럭 단위를 미리 만들어놓는다

• i개를 사용해서 만들 때, 블럭단위에 있는 t개 + dp[i-t]가 최소값인 경우 갱신

---

전체코드

N = int(input())

dp = [1e9]*(N+1)

tetra = [(n*(n+1)*(n+2))//6 for n in range(1,121) if (n*(n+1)*(n+2))//6 <= N]

for t in tetra:
    dp[t] = 1

for i in range(2,N+1):
    for t in tetra:
        if i>t:
            dp[i] = min(dp[i],dp[i-t]+1)
        else:
            break

print(dp[N])

코멘트

• python으로 잘 안돌아감

• $O(100N)$이라 안터질줄 알았는데 터져서 pypy로 풀이