[백준] 11058 크리보드 파이썬

문제

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

11058번: 크리보드

 

크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.

1. 화면에 A를 출력한다.
2. Ctrl-A: 화면을 전체 선택한다
3. Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
4. Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.

크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.

 

---

풀이

 

이모티콘 문제와 유사해서 이리저리 생각해봤다.

이모티콘 문제는 화면에 n개의 이모티콘을 출력하는 데에 걸리는 최소 시간을 출력하는 문제였다.

당시 클립보드와 화면을 이차원 배열로 만들고 그 안에 시간을 저장했었다.

 

이 문제도 유사하지만 n번의 조작을 통해 가장 출력할 수 있는 가장 많은 문자의 개수를 반환해야한다.

그래서 n(시간) 과 다른 하나의 요소로 2차원 배열을 만들어야하나 고민했는데

이렇다 할 풀이 방법이 떠오르지 않아 다른 분 글을 참고했다.

 

https://jokerkwu.tistory.com/172

근데 말도안되게 짧다..ㅠ dp어렵다

DP를 활용해서 문제를 해결할 수 있다.
먼저 초기값으로 i번째 인덱스에는 A를 i번 누른 횟수로 초기화를 하고
 
버퍼에 있는 값을 복사하기 까지 총 3번에 커맨드 횟수가 필요하므로 
컨트롤 v를 한번 두번 세번 누른 최대값을 비교 후 갱신해주면 된다.
 
그 이유는 이미 앞에서 최대값을 갱신했기때문에 커맨드 명령횟수 3번까지만 체크해주면 된다.
dp[i] = max ( dp[i-3]*2, dp[i-4]*3, dp[i-5]*4)  // v를 한 번 누른경우 , 두 번 누른경우 , 세 번 누른경우

n = int(input())
dp = [i for i in range(0, 102)]

for i in range(6, 101):
    dp[i] = max(dp[i-3]*2, max(dp[i-4]*3, dp[i-5]*4))
print(dp[n])

왜 i-5 이전 값은 고려하지 않는지 잘 이해가 안 가서 다른 분의 설명도 가져왔다. (https://loosie.tistory.com/241)

1) 메모이제이션할 변수는 버튼을 누르는 횟수 1개이고 배열 안에 그 횟수안에 출력할 수 있는 A의 최댓값을 담으면 된다.
  ☛ 1차 배열 dp[i] , i : 버튼 누른 횟수 

 

2) 반복문 루프를 하면서 i가 7이상일 때부터는 복사 붙여넣기의 경우의 수를 고려하여 값을 비교해서 최댓값을 갱신해준다.
비교는 간단하게 생각하면 된다.

 

버튼 3회를 누르면 값이 dp[i-3]의 2배로 복사된다. 4회를 누르면 3배, 5회 4배, ..., j회 누르면 j-1배 복사된다.  dp[i] = dp[i-j]*(j-1)

dp[i] = Math.max(dp[i], dp[i-j]*(j-1));
 

3) 점화식 반복문의 범위는 i : 1~n번까지 조회하고, 복사값의 비교는 i>6일 때, j : 3~5까지만 비교해줘도 된다.
이미 dp[0~i]는 최댓값으로 갱신된 값들이기 때문에 모든 값을 비교할 필요없고 새롭게 복붙을 할 수 있는 3회부터 다음 복붙이 가능한 6회 전까지만 비교해줘도 된다.

 

  dp[i] = dp[i-1] +1;   : 기본적으로 화면 A출력을 하면 1개씩 추가가 되니 dp[i-1]+1값을 넣어준다.

for(int i=1; i<n+1; i++) {
	dp[i] = dp[i-1]+1;

	if(i>6) {
		for(int j=2; j<5; j++) {
			dp[i] = Math.max(dp[i], dp[i-(j+1)]*j);
		}
	}
}

조금 이해 갈 것 같다.

3회 i-5 이전 값을 고려하지 않는 것은 그 이전 값은 이미 전의 연산으로 최댓값이 결정된 값이어서 인 것 같다.

 

기본적으로 가감 없이 단순 최댓값이나 최솟값을 찾는 문제는 선형적으로 푸는 방법을 고민해 봐야 하는 것 같다.