[BOJ 23976] 백준 23976번 - 문자열 나누기
| Zero One Algorithm Contest 2021 풀이 | ||
|---|---|---|
| A | [BOJ 23971] ZOAC 4 | |
| B | [BOJ 23972] 악마의 제안 | |
| C | [BOJ 23973] 표적지 옮기기 | |
| D | [BOJ 23974] 짝수 게임 | |
| F | [BOJ 23976] 문자열 나누기 | |
| G | [BOJ 23977] To Find Password | |
| H | [BOJ 23978] 급상승 |
1. 문제
$23976$. 문자열 나누기 (Zero One Algorithm Contest 2021 Open Contest F번)
2. 풀이
$N-1$ 길이의 문자열에서 $N$ 길이의 문자열이 되는 방법은 두 가지가 있다.
- $N$번째 문자를 $N-1$번째 문자가 포함된 연속 부분 문자열에 이어 붙인다.
- $N$번째 문자를 하나의 연속 부분 문자열로 만든다.
매번 두 가지 선택지 중 하나를 선택하여 최적이 되도록 만드는 것이므로 dp를 사용한다.
Leading zero를 예외처리 하려면, $1$번의 경우에서 $N-1$번째 문자가 포함된 연속 부분 문자열이 $0$이면 안 된다. 따라서 어떤 길이까지의 문자열의 처리가 끝났을 때, 맨 마지막에 $0$인 연속 부분 문자열이 있는지 없는지에 대한 정보가 필요하다. 그래서 이 정보를 포함한 dp 배열을 만든다.
-
$dp[n][k][0] \rightarrow$ $n$ 길이의 문자열을 연속 부분 문자열 $k$개로 나누었고, 마지막 연속 부분 문자열이 $0$이 아님
-
$dp[n][k][1] \rightarrow$ $n$ 길이의 문자열을 연속 부분 문자열 $k$개로 나누었고, 마지막 연속 부분 문자열이 $0$임
추가하려는 문자가 $0$인지 $0$이 아닌지에 따라서 연속 부분 문자열 $0$의 생성 및 판단 여부도 달라지기 때문에 이 또한 구분해야 한다.
$(1)$ 추가하는 문자가 $0$이 아닌 경우
$dp[n][k][0]$ $ = dp[n-1][k-1][0] $ $+\; dp[n-1][k-1][1] $ $+\; dp[n-1][k][0]$
- $K-1$개로 나누어진 문자열에 $n$번째 문자($0$이 아님)를 개별 연속 부분 문자열로 추가 $(dp[n-1][k-1][0] $ $+\; dp[n-1][k-1][1])$
- $K$개로 나누어진 문자열의 마지막 연속 부분 문자열에 $n$번째 문자를 이어 붙임. 이때 마지막 연속 부분 문자열이 $0$이면, 이어 붙이지 못함 $(dp[n-1][k][0])$
$dp[n][k][1] = 0$
- 추가하는 문자가 $0$이 아니기 때문에, 마지막 연속 부분 문자열을 $0$으로 만들 수 없다.
$(2)$ 추가하는 문자가 $0$인 경우
$dp[n][k][0]$ $ = dp[n-1][k][0]$
- $K$개로 나누어진 문자열의 마지막 연속 부분 문자열에 $n$번째 문자를 이어 붙임. 이때 마지막 연속 부분 문자열이 $0$이면, 이어 붙이지 못함$(dp[n-1][k][0])$
$dp[n][k][1]$ $ = dp[n-1][k-1][0]$ $ +\; dp[n-1][k-1][1]$
- $K-1$개로 나누어진 문자열에 $n$번째 문자($0$)를 개별 연속 부분 문자열로 추가 $(dp[n-1][k-1][0] $ $+\; dp[n-1][k-1][1])$
최종 답은 $dp[N][K][0] $ $+\; dp[N][K][1]$이 된다.
MOD 주의점
- 마지막에 $dp[N][K][0] $ $+\; dp[N][K][1]$을 계산할 때도
% MOD를 해주어야 한다. - 추가하는 문자가 $0$이 아니면서
dp[i][j][0]을 계산할 때 세 개의 값을 더하게 되는데, 이때integer범위를 넘어갈 수 있다. 따라서dp를long long int로 정의하거나, 두 개 값을 먼저% MOD처리하고 다음 값을 더해서% MOD하는 방식으로 계산한다.
3. 채점 결과
4. 회고
.
댓글남기기