잘못 들어간 자막 문자열 A를 올바른 문자열 B로 고치려 한다.
고치는 일은 세 가지가 있고, 한 번 할 때마다 비용이 든다.
넣기: 글자 하나를 원하는 자리에 끼워 넣는다.
비용은 I이다.
빼기: 글자 하나를 지운다.
비용은 D이다.
바꾸기: 글자 하나를 다른 글자로 바꾼다.
비용은 R이다.
세 가지 일을 원하는 차례로 몇 번이든 해서 A를 B와 똑같게 만들 때, 드는 비용의 합이 가장 작은 값을 출력하라.
A와 B가 처음부터 같으면 0을 출력한다.
1 1 5 abcd abxd
2
3 2 4 banana bandana
3
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
표 dp[i][j] = 'A의 앞 i글자를 B의 앞 j글자로 만드는 가장 작은 비용'으로 푸는 동적 계획법이에요.
마지막 글자를 보면 세 갈래뿐이에요: 같으면 그대로(dp[i-1][j-1]), 다르면 바꾸기(dp[i-1][j-1] + R), A의 i번째 글자 빼기(dp[i-1][j] + D), B의 j번째 글자 넣기(dp[i][j-1] + I) 가운데 가장 작은 것.
첫 예시처럼 R이 크면 바꾸지 않고 빼고 넣는 편(1 + 1 = 2)이 싸요 — 최솟값을 고르니 저절로 처리돼요.
칸 하나는 바로 윗줄과 이번 줄만 보니 두 줄만 들고 다니면 돼요(1,001 × 1,001칸 표 대신 1,001칸 두 개).
함정 하나: 넣기와 빼기를 거꾸로 쓰면 I ≠ D일 때 틀려요 — B에 있는 글자를 새로 쓰는 것(j가 하나 줄어드는 쪽)이 넣기예요.
함정 둘: 첫 줄과 첫 칸은 글자 수가 아니라 j * I(빈 문자열에 모두 넣기)와 i * D(모두 빼기)예요 — 비용이 1인 보통 편집 거리만 생각하고 j, i를 쓰면 틀려요.
함정 셋: 줄 하나에 덮어쓰면 row[j-1]이 이미 이번 줄 값이라 왼쪽 위(대각선) 값을 잃어요 — 두 줄을 쓰거나 대각선 값을 따로 남겨요.
두 줄을 바꾸는 법이 언어마다 달라요: C는 포인터 두 개를 맞바꾸고, C++ std::swap(prev, cur)는 벡터 속만 바꿔 복사가 없고, Java는 배열 참조를, C#은 튜플 (prev, cur) = (cur, prev)로 바꿔요.
Python·JavaScript·TypeScript·크레이콘은 줄마다 새 목록을 만들어 prev = cur로 이어 받아요(크레이콘 새목록(b.길이 + 1, 0)).
글자를 읽는 법도 달라요: Python·JavaScript·TypeScript·C#은 a[i - 1], Java는 a.charAt(i - 1), C는 scanf("%1001s", a)처럼 폭을 정해 배열에 받고, 크레이콘은 콘솔.줄읽기().공백제거()로 받은 문자열의 a[i - 1]이 한 글자 문자열이라 ==로 비교해요.
비용은 많아야 1,000 × 1,000 × 2 = 200만이라 모든 언어에서 int로 충분해요.
import sys lines = sys.stdin.read().split()ins, dele, rep = int(lines[0]), int(lines[1]), int(lines[2])a, b = lines[3], lines[4] # prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(한 줄만 들고 간다)prev = [j * ins for j in range(len(b) + 1)] # 빈 문자열에서 b의 앞 j글자: 모두 넣기for i in range(1, len(a) + 1): cur = [i * dele] + [0] * len(b) # a의 앞 i글자에서 빈 문자열: 모두 빼기 for j in range(1, len(b) + 1): keep = prev[j - 1] + (0 if a[i - 1] == b[j - 1] else rep) # 그대로 두거나 바꾸기 cur[j] = min(keep, prev[j] + dele, cur[j - 1] + ins) # a[i-1] 빼기, b[j-1] 넣기 prev = cur print(prev[len(b)])const [ins, del, rep, a, b] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const I = Number(ins), D = Number(del), R = Number(rep); // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(한 줄만 들고 간다)let prev = Array.from({ length: b.length + 1 }, (_, j) => j * I); // 빈 문자열에서: 모두 넣기for (let i = 1; i <= a.length; i++) { const cur = new Array(b.length + 1); cur[0] = i * D; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (let j = 1; j <= b.length; j++) { const keep = prev[j - 1] + (a[i - 1] === b[j - 1] ? 0 : R); // 그대로 두거나 바꾸기 cur[j] = Math.min(keep, prev[j] + D, cur[j - 1] + I); // a[i-1] 빼기, b[j-1] 넣기 } prev = cur;}console.log(prev[b.length]);import { readFileSync } from "node:fs"; const [ins, del, rep, a, b] = readFileSync(0, "utf8").trim().split(/\s+/);const I = Number(ins), D = Number(del), R = Number(rep); // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(한 줄만 들고 간다)let prev: number[] = Array.from({ length: b.length + 1 }, (_, j) => j * I); // 빈 문자열에서: 모두 넣기for (let i = 1; i <= a.length; i++) { const cur: number[] = new Array<number>(b.length + 1); cur[0] = i * D; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (let j = 1; j <= b.length; j++) { const keep = prev[j - 1] + (a[i - 1] === b[j - 1] ? 0 : R); // 그대로 두거나 바꾸기 cur[j] = Math.min(keep, prev[j] + D, cur[j - 1] + I); // a[i-1] 빼기, b[j-1] 넣기 } prev = cur;}console.log(prev[b.length]);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int ins = Integer.parseInt(st.nextToken()); int del = Integer.parseInt(st.nextToken()); int rep = Integer.parseInt(st.nextToken()); String a = in.readLine().trim(); String b = in.readLine().trim(); // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(두 줄만 번갈아 쓴다) int[] prev = new int[b.length() + 1]; int[] cur = new int[b.length() + 1]; for (int j = 0; j <= b.length(); j++) prev[j] = j * ins; // 빈 문자열에서: 모두 넣기 for (int i = 1; i <= a.length(); i++) { cur[0] = i * del; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (int j = 1; j <= b.length(); j++) { int keep = prev[j - 1] + (a.charAt(i - 1) == b.charAt(j - 1) ? 0 : rep); // 그대로 두거나 바꾸기 cur[j] = Math.min(keep, Math.min(prev[j] + del, cur[j - 1] + ins)); // 빼기, 넣기 } int[] t = prev; // 두 줄을 맞바꾼다(새로 만들지 않는다) prev = cur; cur = t; } System.out.println(prev[b.length()]); }}using System; class Program{ static void Main() { string[] c = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int ins = int.Parse(c[0]), del = int.Parse(c[1]), rep = int.Parse(c[2]); string a = Console.ReadLine().Trim(); string b = Console.ReadLine().Trim(); // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(두 줄만 번갈아 쓴다) var prev = new int[b.Length + 1]; var cur = new int[b.Length + 1]; for (int j = 0; j <= b.Length; j++) prev[j] = j * ins; // 빈 문자열에서: 모두 넣기 for (int i = 1; i <= a.Length; i++) { cur[0] = i * del; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (int j = 1; j <= b.Length; j++) { int keep = prev[j - 1] + (a[i - 1] == b[j - 1] ? 0 : rep); // 그대로 두거나 바꾸기 cur[j] = Math.Min(keep, Math.Min(prev[j] + del, cur[j - 1] + ins)); // 빼기, 넣기 } (prev, cur) = (cur, prev); // 두 줄을 맞바꾼다(새로 만들지 않는다) } Console.WriteLine(prev[b.Length]); }}#include <algorithm>#include <iostream>#include <string>#include <vector> int main() { int ins, del, rep; std::string a, b; std::cin >> ins >> del >> rep >> a >> b; // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(두 줄만 번갈아 쓴다) std::vector<int> prev(b.size() + 1), cur(b.size() + 1); for (size_t j = 0; j <= b.size(); j++) prev[j] = static_cast<int>(j) * ins; // 빈 문자열에서: 모두 넣기 for (size_t i = 1; i <= a.size(); i++) { cur[0] = static_cast<int>(i) * del; // a의 앞 i글자에서 빈 문자열: 모두 빼기 for (size_t j = 1; j <= b.size(); j++) { int keep = prev[j - 1] + (a[i - 1] == b[j - 1] ? 0 : rep); // 그대로 두거나 바꾸기 cur[j] = std::min({keep, prev[j] + del, cur[j - 1] + ins}); // 빼기, 넣기 } std::swap(prev, cur); // 벡터 속만 맞바꾼다(복사하지 않는다) } std::cout << prev[b.size()] << "\n";}#include <stdio.h>#include <string.h> #define MAXL 1000 static char a[MAXL + 2], b[MAXL + 2];static int row0[MAXL + 1], row1[MAXL + 1]; static int min3(int x, int y, int z) { int m = x < y ? x : y; return m < z ? m : z;} int main(void) { int ins, del, rep; scanf("%d %d %d", &ins, &del, &rep); scanf("%1001s %1001s", a, b); int n = (int)strlen(a), m = (int)strlen(b); /* prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(두 줄만 번갈아 쓴다) */ int* prev = row0; int* cur = row1; for (int j = 0; j <= m; j++) prev[j] = j * ins; /* 빈 문자열에서: 모두 넣기 */ for (int i = 1; i <= n; i++) { cur[0] = i * del; /* a의 앞 i글자에서 빈 문자열: 모두 빼기 */ for (int j = 1; j <= m; j++) { int keep = prev[j - 1] + (a[i - 1] == b[j - 1] ? 0 : rep); /* 그대로 두거나 바꾸기 */ cur[j] = min3(keep, prev[j] + del, cur[j - 1] + ins); /* 빼기, 넣기 */ } int* t = prev; /* 포인터만 맞바꾼다 */ prev = cur; cur = t; } printf("%d\n", prev[m]); return 0;}비용 = 콘솔.수들읽기();ins = 비용[0];del = 비용[1];rep = 비용[2];a = 콘솔.줄읽기().공백제거();b = 콘솔.줄읽기().공백제거(); // prev[j] = a의 앞 i-1글자를 b의 앞 j글자로 바꾸는 가장 적은 비용(한 줄만 들고 간다)prev = [];반복 (j = 0; j <= b.길이; j++){ prev.넣기(j * ins); // 빈 문자열에서 b의 앞 j글자: 모두 넣기}반복 (i = 1; i <= a.길이; i++){ cur = 새목록(b.길이 + 1, 0); cur[0] = i * del; // a의 앞 i글자에서 빈 문자열: 모두 빼기 반복 (j = 1; j <= b.길이; j++) { keep = prev[j - 1] + rep; // 다른 글자로 바꾸기 만약 (a[i - 1] == b[j - 1]) { keep = prev[j - 1]; // 같은 글자는 그대로 둔다 } cur[j] = 수학.작은수(keep, 수학.작은수(prev[j] + del, cur[j - 1] + ins)); // 빼기, 넣기 } prev = cur;}콘솔.쓰기(prev[b.길이]);