https://www.acmicpc.net/problem/2195
2195번: 문자열 복사
첫째 줄에 S, 둘째 줄에 P가 주어진다. S와 P는 영어 대소문자와 숫자로만 되어 있다. S의 길이는 1,000을 넘지 않으며, P의 길이는 1,000을 넘지 않는다. copy함수만을 이용하여 S에서 P를 만들어낼 수
www.acmicpc.net
📌 작성한 코드
// 2195
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 s = input[0];
const p = input[1];
// 간단하게 풀기
let temp = "";
let answer = 1;
for (let i = 0; i < p.length; i++) {
const next = temp + p[i];
if (s.indexOf(next) !== -1) {
temp = next;
} else {
temp = p[i];
answer++;
}
}
console.log(answer);
// dp 사용하기
const dp = Array(p.length + 1).fill(Infinity);
dp[0] = 0;
const possible = new Set();
for (let i = 0; i < p.length; i++) {
for (let j = 0; j <= i; j++) {
const remain = p.slice(i - j, i + 1);
if (possible.has(remain) || s.indexOf(remain) !== -1) {
dp[i + 1] = Math.min(dp[i + 1], dp[i - j] + 1);
possible.add(remain);
}
}
}
console.log(dp[p.length]);
📌 설명
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/DP] 백준 골드 5 : 5557 - 1학년 (0) | 2024.04.11 |
|---|---|
| [JavaScript/BFS] 백준 골드 4 : 14226 - 이모티콘 (0) | 2024.04.09 |
| [JavaScript/DP] 백준 골드 5 : 2410 - 2의 멱수의 합 (0) | 2024.03.26 |
| [JavaScript/DP] 백준 골드 4 : 14002 - 가장 긴 증가하는 부분 수열 4 (1) | 2024.03.26 |
| [JavaScript/구현] 백준 골드 3 : 16236 - 아기 상어 (0) | 2024.03.20 |