BOJ(크리보드)(11058)

작성일 | In

크리보드 (11058)

  • 점화식을 정의해보자.
  • D[N]: 버튼을 n번 눌러서 화면에 출력되는 경우의 수를 최대로 하고 싶다
  • D[N]: 버튼을 n번 눌러, 화면에 출력된 A의 최대 개수
  • 마지막에 누른 버튼이 어떤 것인지에 따라서 A의 개수가 변하게 된다.
  • D[n] : 마지막에 1번을 누른 경우 -> 화면에 있는 버튼의 개수가 D[n-1] +1
  • 문제는 아래 3가지 버튼, Ctrl-A와, Ctrl-C는 내용에 변화가 없다.

  • 2번과 3번과 4번 버튼은 어떻게 처리하면 좋을까.

  • Ctrl-v를 하려면 버퍼가 비어있지 않아야 한다 -> Ctrl+c를 먼저 눌러야 한다
  • Ctrl+c를 누르려면 Ctrl+a를 먼저 눌러야 한다

  • 즉 Ctrl + A , Ctrl + C, Ctrl + V는 꼭 연속을 눌러야 의미가 있다.

  • ?,?,?, Ctrl+A, Ctrl+C, Ctrl+V를 누르는게 있다고 하자. 이 버튼은 총 N번 누른상태다.
  • 이 때 화면에 출력된 전체 A의 개수가 D[N]개
  • 즉 ?,?,?는 -> N-3 번 누른 상태다. 이 때 A의 최대 개수는 D[N-3]개다.

  • 이 상태에서 ctrl + A, ctrl +c, ctrl +v를 눌렀으면 D[N-3]*2가 되어야 한다

  • 그런데 Ctrl+A를 두번 누르는건 의미가 없다.
  • 복사를 두번 누르는 경우는 어떻게 될까? -> 버튼을 최소로 누를 거면 이 경우도 모두 빼줘야 한다
  • Ctrl+V를 두번 누르는 경우는 유의미하다.
  • ?,?,?,Ctrl+A, Ctrl+C, Ctrl+V 그런데, 한번더 Ctrl+V를 눌렀다면, 이게 총 N번 이었다면,
  • ?는 D[N-4]개. 이게 A의 최대 개수.
  • 이 때 컨트롤 V를 두번 눌렀다면 D[N-4]*3을 한게 된다.
  • 계속 누르는 경우가 있을 수 있다.

일반화

  • D[i] = 크리보드의 버튼을 총 i번 눌러서 화면에 출력된 A개수의 최댓값
  • 화면에 A를 출력하는 버튼을 누른 경우: D[i-1]+1
  • 마지막에 Ctrl +A, Ctrl+C, Ctrl+V를 누른 경우 : D[i-3]*2
  • 마지막에 Ctrl +A, Ctrl+C, Ctrl+V, Ctrl+V를 누른 경우 : D[i-5]*4
  • 마지막에 Ctrl +A, Ctrl+C, Ctrl+V, Ctrl+V, Ctrl+V를 누른 경우 : D[i-(j+2)*(j+1)]
  • D[i] = max(D[i-1]+1,D[i-(j*2)]*(j+1))(1<=j<=i-3)
  • 앞은 A를 출력, 뒤는 j번 ctrl+v를 누르는 경우
  • n개의 칸을 채워야 하는데 n개의 루프를 돔. N^2
n = int(input())
d = [0] * (n+1)
for i in range(1, n+1):
    d[i] = d[i-1] + 1
    for j in range(1, i-3+1):
        cur = d[i-j-2]*(j+1)
        d[i] = max(cur, d[i])
print(d[n])

참고자료 codeplus

0%