어찌저찌 풀어냈는데 고작 실버면 한숨
정답율 50% 육박하거나 넘어서면 한숨 두번
여러모로 양심없는 유형이다
욕을 적고 싶지만 참고 포스팅 해보겠다
해당 문제는 n=100이라고 가정할 때 4가지의 선택을 100번 해야하므로 O(4^100)의 시간복잡도가 걸린다. 따라서 dp를 통해 시간을 단축해서 풀어야한다.
일단 최종 n번을 눌렀을 때 A의 최댓값을 구하는 것이므로 dp테이블의 크기는 n+1로 생성해주며, dp는 아래의 사이클을 돌며 업데이트 될 것이다.
1번 눌렀을 때 A의 최댓값
2번 눌렀을 때 A의 최댓값
...
n번 눌렀을 때의 A의 최댓값
이런 식으로 나아가다 보면 최종 값에 도달할 수 있다.
먼저 A를 출력할 수 있는 방법은 무엇일까?
선택
- ctrl+c
- ctrl+v
까지 3단계를 거쳐 버퍼에 있는 내용을 붙이거나 ( 👉🏻 계산하면 dp[i-3]*2가 될 것이다)이제 완전한 점화식을 만들기 위해 조금 더 생각해보자.
유심히 생각해보면 버퍼에 있는 내용을 붙일 수 있는 최소 조건이 3단계인 것이지, 우리는 4단계 이전의 값을 복사해서 붙여넣을 수도 있을 것이다. 그렇게 되면 dp[i-4]*2가 된다.
5단계는 될 수 없을까? 당연히 가능하다. dp[i-5]*2가 될 것이다.
그렇다면 6은? 6을 넘어가고서부터는 그냥 출력 버튼을 바로 누르는 것이 더 크기 때문에 고려하지 않는다. (사투 끝에 알아낸 원리..)
따라서 최종 점화식은 아래와 같다
dp[i] = max(dp[i],dp[i-j]*(j-1))
사실 점화식만 보면 이해가 안 될수도 있으므로 아래 전체 코드의 주석을 통해 다시 한 번 확인해보자.
import sys
input = sys.stdin.readline
n = int(input())
dp = [0] * (n + 1)
for i in range(1, 7): # 6이하는 그냥 하나씩 출력하는 것이 최댓값임
if i <= n:
dp[i] = i
for i in range(7, n + 1): #7부터는 점화식에 따라 dp 업데이트 진행
for j in range(3, i): #붙여넣는 것은 3단계가 필요하므로 최소 3부터 시작
if i - j > 0:
dp[i] = max(dp[i], dp[i - j] * (j - 1))
print(dp[n])