11058 크리보드

https://www.acmicpc.net/problem/11058

11058번: 크리보드

#11058 크리보드

n=int(input())
#n 입력

dp=[i for i in range(n+1)]
#dp 생성

for i in range(7,n+1):
    for j in range(i):
        if dp[i-(3+j)]*(2+j) > dp[i-(3+j+1)]*(2+j+1):
            dp[i]=dp[i-(3+j)]*(2+j)
            break
        
print(dp[n])
#출력

# a만 누른자, 이전껄 복사해서 넣은 자, 이전꺼보다 1 작은걸 복해서 넣고 복붙 다시 한 자 이렇게 있네
#고로 1을 추가하는게 나을지 아니면 (i-3)*2 가 나을지 (i-(3+j))*(2+j) 이게 나을지 보면 될듯 7부터 조건 1 삭제

 

#기본적인 dp 문제이자 조건을 생각하고 나누는게 얼마나 중요한지 알려준 문제, 이전의 dp의 경우에는 이중리스트와 부울 함수를 이용하여 메모리초과 문제를 해결했다면 이번 문제는 100개 밖에 안되기 때문에 직접 숫자를 dp에 넣었다는 점은 주목할만 하다.