[JavaScript/DP] 백준 골드 5 : 11058 - 크리보드

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

11058번: 크리보드

---

📌 작성한 코드 

// 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번으로 가능한 이유

 

✅ 성공