https://www.acmicpc.net/problem/11058
11058번: 크리보드
N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl
www.acmicpc.net
📌 작성한 코드
// 11058
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const N = Number(input.shift());
const dp = Array(N + 1).fill(0);
for (let i = 1; i <= 6; i++) {
dp[i] = i;
}
for (let i = 7; i <= N; i++) {
dp[i] = Math.max(dp[i - 3] * 2, dp[i - 4] * 3, dp[i - 5] * 4);
}
console.log(dp[N]);
📌 설명
크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력하는 문제이다.
할 수 있는 행동은 4가지가 존재한다.
1. A를 1개 추가하기
2. 전체를 선택하기
3. 선택한 만큼 복사하기
4. 복사한 내용 붙여넣기
할 수 있는 행동은 4가지지만 실제로 문자열을 붙여넣기(4번의 행동) 위해서는 2,3의 과정을 꼭 거쳐야만 가능하다.
하지만 매번 2,3의 과정을 거쳐야만 하는 것은 아니다. 버퍼에 문자열이 이미 복사되어 있다면 해당 내용을 바로 붙여넣기(4번)하는 것도 가능하다.
해당 내용에 따라서 버튼을 i번 눌러서 만들 수 있는 값을 구하는 방법은 4가지가 존재한다.
- 1~6까지는 복사 붙여넣기 해서 값을 만드는 것보다 0번의 활동을 통해 +1 하는게 더 큰 값을 만들 수 있으므로 7부터 해당 계산을 적용하였다.
- 선택 - 복사 - 붙여넣기 3번의 클릭이 필요하기 때문에 복사 붙여넣기를 사용한다면 6번 클릭시 최대 3정도 밖에 만들어지지 않는다.
0. i-1번의 결과에 1을 더하는 경우 (+1을 해서 최댓값을 만들어내는 것은 불가능하기 때문에 실제 고려하지 않음)
1. i-3번 결과(A 개수 최댓값)의 2배 (i-3번의 결과를 복사해서 붙여넣은 결과)
2. i-4번 결과의 3배 (i-4번의 결과를 2번 붙여넣은 결과)
3. i-5번 결과의 4배 (i-5번의 결과를 3번 붙여넣은 결과)
✍️ 붙여넣기를 4번 이상 하는 경우를 고려하지 않는 이유
: 아래 블로그에서 귀납적으로 계산하는 결과를 확인할 수 있다.
https://blog.naver.com/mym0404/222323009491
백준 11058 크리보드 - 붙여넣기 3번으로 가능한 이유
다이나믹 프로그래밍 문제인데 좀 사투를 벌였다. 다른 사람들은 쉽게 푸나보다. 이러 유형이 dp인지 그리...
blog.naver.com
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/BFS] 백준 골드 4 : 2636 - 치즈 (1) | 2024.04.19 |
|---|---|
| [JavaScript] 백준 골드 5 : 20165 - 인내의 도미노 장인 호석 (2) | 2024.04.18 |
| [JavaScript/DP] 백준 골드 5 : 5557 - 1학년 (0) | 2024.04.11 |
| [JavaScript/BFS] 백준 골드 4 : 14226 - 이모티콘 (0) | 2024.04.09 |
| [JavaScript/DP] 백준 골드 5 : 2195 - 문자열 복사 (0) | 2024.03.28 |