BOJ 11058 크리보드

누를 수 있는 버튼이 4가지가 있는데,
1. A를 출력하는 버튼 (A)
2. 현재 화면의 A를 모두 선택하는 버튼 (Ctrl-A)
3. 선택한 내용을 버퍼에 복사하는 버튼 (Ctrl-C)
4. 버퍼에 있는 내용을 붙여넣는 버튼 (Ctrl-V)

그냥 간단히 말해서 키보드에서 A, Ctrl-A(전체 선택), Ctrl-C(복사), Ctrl-V(붙여 넣기) 이렇게 4가지 기능만 사용가능하다고 할 때, 이 4가지 기능 중에서 적절히 선택하여 N번 기능을 사용했을 때, 화면에 출력할 수 있는 A의 개수의 최대값을 구하는 문제이다.

무조건 1번 기능만 사용해서는 최대 N개인데, N이 작은 경우는 1번 기능만 사용하는 것이 A를 화면에 최대로 나오게 할 수 있겠지만, N이 일정 크기 이상일 경우에는 Ctrl-A, Ctrl-C, Ctrl-V 즉, 2, 3, 4를 반드시 사용해야 최대가 될 수 있다. 하지만 어떻게 써야 최대가 될지는 딱 감이 오는 것이 없다. 가능성 있는 모든 경우를 다 해봐야할 것 같다. dp로 접근해보자.

d[n]=버튼을 n번 눌러서 출력할 수 있는 A개수의 최대값....? 음 하지만 최대값으로 해버리면, d[n]이 최대가 되기 위해 d[n-1]이 최대값이 아니여야 할 수도 있기 때문에... 조건을 하나 더 넣어야 할 것 같다.
d[n][현재 버퍼에 있는 A의 개수?.... 음 어렵다.
한 번 다시 생각해보자.

d[n][bt] = n번째 버튼을 bt를 눌렀을 때, A개수의 최대값
d[n][bt] = MAX(nbt : 1~4, d[n+1][nbt]+(bt==1이면 +1, bt==4이면 버퍼에 있는 만큼..))
음... 이것으로는 부족하다. 버퍼에 얼마나 있는지도 알아야 한다. 생각해보자.
일단 최대가 되기 위함을 생각하면, 2. 전체 선택과 3. 복사 버튼은 항상 함께 써야한다.
2, 3을 썼다면 4. 붙여 넣기를 써야하는데, 4. 붙여 넣기 버튼은 쓸 때마다 버퍼에 있는 만큼 화면에 나오게 되고, 즉, 다음에 버퍼에 들어갈(2, 3을 눌러야 들어감) A의 개수가 (4. 붙여 넣기를 쓴 횟수 * 지금 버퍼에 있는 A의 개수 + 현재 화면에 있는 A의 개수)가 될 것이다.
그리고 2, 3을 한 번 쓸 때마다 그 것들이 버퍼에 복사되고... 그럼 현재 버퍼에 몇 개가 있는지도 기록해야하고 이 것은 메모이제이션이 되려나...음 안 될 것 같은...배열의 인덱스로 버퍼에 있는 것의 개수를 잡자니 n이 최대 100이라 수가 너무 커져서 불가능하다.

좀 더 간단하게 만들어 보자.
A를 출력하는 버튼은 1번 버튼 혹은 4번 버튼 뿐이다. 그리고 2, 3 버튼은 두 개가 항상 같이 쓰여야 한다고 볼 수 있다.
결국 버튼은 3개로 볼 수 있다. (1), (2, 3), (4)...
그리고 맨 처음에는 무조건 1번 버튼을 써야하고...

--------------------------------------------------------------------------------

음 도저히 생각이 안난다. 잠시 쉬다가 생각해보니, 현재 버퍼에 있는 것은 현재까지 출력되어 있는 것의 개수로도 볼 수가 있지 않나? 그렇다면 아예 d배열에 기록된 것을 사용하면 될 것이다. 아니다. 다시 생각해보니 현재까지 출력되어 있는 것의 개수를 (가장 최근까지 연속해서 사용한 4번 버튼의 개수)로 나눈 값이 버퍼에 있는 값이 될 것이다. 그렇다면
(가장 최근까지 연속된 4번 버튼의 개수)도 인자로 넣야할 것이다.
d[n][bt][con]=n번째 버튼 bt를 눌렀을 때, 그리고 n-1번째까지 가장 최근에 4번 버튼을 연속해서 con개 눌렀을 때, A개수의 최대값
d[n][bt][con]=MAX(nbt:1~4, con_pre는 nbt에 따라 con-1 or con,  
d[n-1][nbt][con_pre]+(bt==1이면 +1, bt==4이면 d[n-1][bt][con_pre]/con) )
그리고 답으로는 d[n][4][1~n]중 최대값을 구하면 될 것이다. 
                                                                                                   

다시 다시 다시...
결국 풀이를 보기로 했다. 내 힘으로 못 푼다는 것이 참 아쉽고 슬프지만, 그리고 여전히 dp를 무서워 한다는 것이 참 슬픈일이지만... 그냥 너무 아쉽다. 진짜 dp를 정복해보자. 1일 3dp가자...

일단 백준님의 풀이의 앞 부분을 보니
d[n]=크리보드를 n번 눌러서 화면에 출력된 A개수의 최대값
이라고 나와있다. 여기서부터 생각해보자.
근데 내가 처음 생각할 땐, 예를 들어 d[n]이 최대값이기 위해 d[n-1]은 최대값이 아니여야 할 수도 있어서 이것은 아닌 것 같다고 결론내렸는데... 풀이를 더 봐야겠다.

음 어느정도 이해했다. 확실히 와 닿지는 않지만...
d[n]에서 n이 작을 때는, 그냥 A만 누르는 것이 나을 수도 있지만, n이 어느정도 클 때, A의 개수가 최대가 되도록 하려면, 반드시 Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V...를 써야할 것이다.
이 때, Ctrl-V를 몇 번 쓰다가 Ctrl-A, Ctrl-C, Ctrl-V...를 써야할지는 해봐야한다.
그리고 Ctrl-V의 개수가 늘어남에 따라 Ctrl-A, Ctrl-C에서 버퍼에 저장된 개수도 비례해서 늘어난다. 

그래서 j를 (Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, ..., 한 번 복사해서 붙여넣기를 하는 데 드는 횟수)라고 하면 d[n]=크리보드를 n번 눌러서 화면에 출력된 A개수의 최대값 이므로,
d[n]=MAX(d[n-1]+1, d[n-j]*(j-1) , j는 3이상 n-1이하 ) 이 된다.
d[n-1]+1은 마지막이 A누르는 것으로 끝나는 경우이다. (Ctrl-A, Ctrl-C를 누르는 데 2번은 걸리니까, n이 작을 때는 그냥A를 누르는 게 나은 경우가 있다.)
d[n-j]는 (Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V,...)를 누르기 전까지의 상태를 의미한다. 즉, n-j번 눌러서 화면에 출력된 A개수의 최대값인데, d[n-j]에 j-1을 곱하는 이유는 뭘까?
n-j번 누른 이후, j번을 누르는데, 그 중 2번은 Ctrl-A, Ctrl-C를 누르는 데 사용된다. 그렇다면 Ctrl-V는 j-2번 누를 수 있는데, d[n-j]*(j-2)만큼 A의 개수가 증가하게 되고, 결국 원래 있던 d[n-j]와 합치면 d[n-j]*(j-1)이 되는 것이다.

내가 원래 처음에 d[n]=크리보드를 n번 눌러서 화면에 출력된 A개수의 최대값 <-에서 더 이상 나가지 못했던 이유가, d[n]이 최대값이 되려면, d[n-1]같이 d[n]전에 있는 값들은 최대값을 가지면 안되는데... 하고 걱정했었다. 하지만, d[n]을 구하는 데 필요한 값들을 아무거나 갖다 쓰는게 아니라, (Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V,...) 단위로 끊어서 보기 때문에 괜찮다. 예를 들어, (Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V...)에서 중간에 Ctrl_A지점에서 끊어버리면 내가 위에서 걱정했던 문제가 발생할 수 있다. Ctrl-A로 끝나느니, 그 이전의 Ctrl-V를 한 번 더 하고 끝나는 게 낫기 때문이다. 하지만 저렇게 (Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, ...) 단위로 끊어서 모든 경우를 다 해보면서 그런 문제는 생각하지 않아도 된다.

이렇게 쓰다보니 그래도 어느정도 이해가 되는데, 아직도 100%라고는 못하겠다.
열심히 하자.

출처 : 백준님 강의 자료 풀이