[BAEKJOON] 2602 돌다리 건너기

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <string> using namespace std; int main() { string answer, angel, devil; cin >> answer >> angel >> devil; vector<vector<long long>>Angel(101, vector<long long>(101, 0)), Devil(101, vector<long long>(101, 0)); int ans_count = answer.size(); int bridge_count = angel.size(); Angel[0][0] = 1; Devil[0][0] = 1; for (int x = 1; x <= ans_count; x++) { for (int y = 1; y <= bridge_count; y++) { if (answer[x - 1] == angel[y - 1]) for (int k = 0; k <= y - 1; k++) Angel[x][y] += Devil[x - 1][k]; if (answer[x - 1] == devil[y - 1]) for (int k = 0; k <= y - 1; k++) Devil[x][y] += Angel[x - 1][k]; } } long long answer_count = 0; for (int j = 0; j <= bridge_count; j++) answer_count += (Angel[ans_count][j] + Devil[ans_count][j]); printf("%lld", answer_count); return 0; }

문제를 푸는 방법은 간단하다

단지 내가 생각을 못했을뿐..

이런식으로 풀면 되겠구나

알고리즘도 공부라고 생각하는데도

막생 내가 풀지 못하면 우울하다..

오늘은 여기까지 풀어야겠다!