2개의 행, 같은 길이의 열로 존재하는 돌다리에 대문자 알파벳이 적혀있다.
그리고 꼭 밟고 건너가야 하는 문자열이 추가로 주어질 때 각 문자를 윗다리,아랫다리
번갈아 가며 건너가야 한다.
윗다리, 아랫다리를 번갈아가며 가기에 기준을 윗다리와 아랫다리 두개로 나누었고
꼭 밟아야 하는 문자열을 또 하나의 기준으로 삼았다.
DP[0][M][S] = 윗다리 기준으로 M만큼이동 하였을 때 꼭 밟아야 하는 문자열의 S까지
밟을 수 있는 경우의 수
DP[1][M][S] = (아랫다리 기준)이하 위와 동일
#include <cstdio>
#include <cstring>
int dp[2][101][21];
int main(){
char must[21];
char angel[101], devil[101];
int must_len, len;
scanf("%s\n%s\n%s", must, angel, devil);
must_len = strlen(must);
len = strlen(angel);
int angel_cnt = 0, devil_cnt = 0;
for (int n = 0; n <= len ; n++){
if (angel[n] == must[0]){
dp[0][n][0] = angel_cnt;
angel_cnt++;
}
else{
dp[0][n][0] = angel_cnt;
}
if (devil[n] == must[0]){
dp[1][n][0] = devil_cnt;
devil_cnt++;
}
else{
dp[1][n][0] = devil_cnt;
}
}
for (int n = 1; n < must_len; n++){
for (int m = 0; m < len; m++){
if (n & 1){
if (devil[m] == must[n] && dp[0][m][n-1] > 0){
dp[0][m + 1][n] = dp[0][m][n - 1] + dp[0][m][n];
}
else if (devil[m] != must[n]){
dp[0][m + 1][n] = dp[0][m][n];
}
if (angel[m] == must[n] && dp[1][m][n - 1] > 0){
dp[1][m + 1][n] = dp[1][m][n - 1] + dp[1][m][n];
}
else if (angel[m] != must[n]){
dp[1][m + 1][n] = dp[1][m][n];
}
}
else{
if (angel[m] == must[n] && dp[0][m][n - 1] > 0){
dp[0][m + 1][n] = dp[0][m][n - 1] + dp[0][m][n];
}
else if (angel[m] != must[n]){
dp[0][m + 1][n] = dp[0][m][n];
}
if (devil[m] == must[n] && dp[1][m][n - 1] > 0){
dp[1][m + 1][n] = dp[1][m][n - 1] + dp[1][m][n];
}
else if (devil[m] != must[n]){
dp[1][m + 1][n] = dp[1][m][n];
}
}
}
}
printf("%d\n", dp[0][len][must_len - 1] + dp[1][len][must_len - 1]);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기