문제 링크
문제
티어: 골드 1
알고리즘: dp
'유사 바나나 문자열'은 '유사 바나나' 한 개 이상을 이용하여 임의의 순서로 이어 붙인 문자열을 말한다. '유사 바나나'는 다음과 같이 정의된다.
- BANANA는 '유사 바나나'이다.
- ‘유사 바나나' 앞에 B를 붙인 것 또한 '유사 바나나'이다. 예를 들어, BBANANA는 '유사 바나나'이다.
- '유사 바나나' 뒤에 NA를 붙인 것 또한 '유사 바나나'이다. 예를 들어, BANANANA나 BBANANANA는 '유사 바나나'이다.
BBANANA와 BANANANA는 '유사 바나나'이므로, BBANANABANANANA와 BANANANABBANANA는 모두 '유사 바나나 문자열'이다. 또한 BBANANA와 BANANANA도 정의에 의해 '유사 바나나 문자열'에 속한다. BANANAABANANA의 경우는 '유사 바나나'가 두 개 포함되었지만 BANANA와 BANANA 사이에 A가 포함되어 있고, 그 결과 '유사 바나나 문자열'이 될 수 없다.
B, A, N으로 이루어진 문자열이 주어질 때, 이 문자열을 '유사 바나나 문자열'로 만들기 위해서 문자를 바꾸는 횟수의 최솟값을 구하는 프로그램을 작성하여라.
입력
'유사 바나나 문자열'로 바꾸고 싶은 길이 M의 문자열이 공백 없이 주어진다. M은 6 이상 100000 이하의 수이다.
출력
입력에서 주어진 문자열을 '유사 바나나 문자열'로 만들기 위해서 문자를 바꾸는 횟수의 최솟값을 출력한다. '유사 바나나 문자열'로 바꿀 수 없는 경우는 존재하지 않는다.
풀이
유사 바나나 문자열로 만들기 위해서 문자를 바꾸는 횟수의 최솟값을 출력해야 한다.
만약 길이가 6이라면 존재하는 유사 바나나 문자열은 "BANANA" 하나다.
만약 길이가 같은 유사 바나나 문자열이 여러 개라면 그 중 최소 횟수만을 가진 유사 바나나 문자열만을 취급하면 된다. 왜냐하면 "NA", "BANANA"를 붙인다 했을 때 어떤 바나나 문자열이라도 똑같기 때문이다.
예를 들어 "BBBANANA"와 "BANANANA"는 길이가 같은 바나나 문자열인데, 이 중 전자가 최소 횟수라면 후자의 경우는 따져주지 않아도 된다.
그런데 중요한 점은 "B"를 붙이는 연산이다. B는 바나나 문자열 앞에 붙이는 연산이기 때문에 앞에 상태를 변경시켜 항상 그 값이 최선이 아닐 수 있게 된다.
이를 해결하기 위해 새로운 자리가 추가되었을 때 B를 붙이는 모든 경우를 따져보면,
xxxxxxxxBANANA (마지막이 새로운 자리라 했을 때)
xxxxxxxBBANANA
xxxxxxBBBANANA
이렇게 세 가지 경우가 존재한다.
여기서 문제점은 새로운 자리가 추가될 때마다 모든 B를 따져준다면, 문자열은 최대 10만이기 때문에 TLE가 발생할 것이다.
그래서 패턴을 발견해야 되는데,
앞에 세 가지 경우에서 가장 작은 값이 가운데에 있는 xxxxxxxBBANANA 라면, 다음에는 모든 B를 따지는 것이 아닌 xxxxxxxBBANANA이 경우에서 B가 추가된 경우인 xxxxxxxB(B)BANANA와 xxxxxxxxxBANANA만 따져주면 된다. 그 이유는 다음과 같다.
앞의 세 가지 문자열을 BANANA를 기준으로 나눠보면,
xxxxxxxxB
xxxxxxxBB
xxxxxxBBB
가 되는데, 다음 새로운 자리가 추가되었을 때 결국 이 문자열에 B가 추가되는 형태인 다음과 같다.
xxxxxxxxB(B)
xxxxxxxBB(B)
xxxxxxBBB(B)
그래서 세 가지 중 가장 작은 값만을 유지하고, 이후에 새롭게 추가되는 xxxxxxxxxBANANA와 비교해서 더 작은 값을 계속 유지해 나가면 된다.
위 풀이를 토대로 dp를 정의하면 dp[A]이며, A는 문자열 맨 왼쪽부터 A까지 바나나 문자열로 만들기 위해서 문자를 바꾸는 횟수의 최솟값을 뜻한다.
그래서 앞에서부터 dp를 채워나가고, 새로운 자리가 추가되었을 때 예를 들어 dp[11]를 구하고 dp[12]를 구할 때 모든 경우의 수인
- 11, 12번째 NA일 때 횟수 + dp[10]
- xxBANANA를 붙였을 때 최소 횟수 + dp[4]
를 따져서 최소 횟수를 넣어주면 된다.
이 풀이의 시간 복잡도는 O(M.length())다.
소스 코드
import java.io.*;
public class Main {
static int N;
static final int MAX = 1000001;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String inputStr = " " + br.readLine();
N = inputStr.length() - 1;
String bStr = "BANANA";
int[] dp = new int[N + 1];
init(dp);
dp[6] = findChange(1, 6, inputStr, bStr);
for(int i=7; i<=11; i++) {
if(N < i) {
System.out.println(dp[N]);
return;
}
int NA = findChange(i - 1, i, inputStr, "NA");
dp[i] = Math.min(dp[i], dp[i - 2] + NA);
bStr = "B" + bStr;
int B = findChange(1, i, inputStr, bStr);
dp[i] = Math.min(dp[i], B);
}
int minB = findChange(1, 5, inputStr, "BBBBB");
for(int i=12; i<=N; i++) {
//NA를 붙이는 경우
int NA = findChange(i - 1, i, inputStr, "NA");
dp[i] = Math.min(dp[i], dp[i - 2] + NA);
//BANANA를 붙이는 경우
if(inputStr.charAt(i - 6) != 'B') {
minB += 1;
}
minB = Math.min(minB, dp[i - 6]);
int BANANA = findChange(i-5, i, inputStr, "BANANA");
dp[i] = Math.min(dp[i], minB + BANANA);
}
System.out.println(dp[N]);
}
static int findChange(int s, int e, String str, String tStr) {
int result = 0;
for(int i=s; i<=e; i++) {
if(str.charAt(i) != tStr.charAt(i - s)) {
result += 1;
}
}
return result;
}
static void init(int[] dp) {
for(int i=0; i<dp.length; i++) {
dp[i] = MAX;
}
}
}