파이썬 백준 11058번: 크리보드

문제

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

11058번: 크리보드

 

 

풀이

출력개수를 담은 d배열을 정의하고 최댓값으로 업데이트하였다. 

🤔1~6일 경우 복사-붙여넣기를 하지 않고 그대로 출력하는 경우가 최대이다.( 3번 누른 후 Ctrl-A, Ctrl-C, Ctrl-V =>6번)
🤔 7보다 클경우 붙여넣기를 통해 큰 값이 있는지 판단해야한다. 

      복사-붙여넣기를 한번만 하는 경우, "선택-복사-붙여넣기" 로 인해 3번이 소요되고, 값은 2배가 된다 : d[i-3]*2

      복사-붙여넣기를 두번 하는 경우, "선택-복사-붙여넣기-붙여넣기" 로 인해 4번이 소요되고, 값은 3배가 된다 : d[i-4]*3

      복사-붙여넣기를 세번 하는 경우, "선택-복사-붙여넣기 -붙여넣기 -붙여넣기" 로 인해 5번이 소요되고, 값은 4배가 된다

확인해보면 k번이 소요되면 값이 (k-1)번 된다고 할 수 있다. 

따라서 while문을 통해 k가 i이상 되지 않는 경우 최댓값을 계산해서 갱신하도록 했다. 

import sys

d=[0]*101
N=int(sys.stdin.readline())
for i in range(1,N+1):
    d[i]=d[i-1]+1
    if i>=7:
        k=3
        while(k<i):
            d[i]=max(d[i],d[i-k]*(k-1))
            k+=1
print(d[N])

 

 

덧)

다른사람의 풀이를 확인해보니 붙여넣기는 최대 3번까지 확인하면 된다고 한다!

참고 블로그 : https://blog.naver.com/mym0404/222323009491

백준 11058 크리보드 - 붙여넣기 3번으로 가능한 이유