3143. 가장 빠른 문자열 타이핑
이 문제는 원래 단어 한개씩 치다가, 치트키가 있는 경우 여러단어를 한꺼번에 칠 수 있다.
그리고 최솟값을 구해야 하기 때문에, 최단거리 그래프 문제로 보고 다익스트라 알고리즘을 사용했다.
단순히 BFS로 구현해도 될 것 같다.
그래서 매번 현재 위치에서 + 1 을 하거나, 치트키가 가능한 경우는 가능한 만큼 넘어가면 된다.
<정답 코드 - 다익스트라>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include<iostream> #include<string> #include<queue> using namespace std; const int INF = 987654321; int main() { int tc; cin >> tc; for (int t = 1; t <= tc; t++) { string A = "", B = ""; cin >> A >> B; priority_queue<pair<int,int>> q; vector<int> dist(10001, INF); dist[0] = 0; q.push({ dist[0],0 }); while (!q.empty()) { int cost = -q.top().first; int now = q.top().second; q.pop(); if (cost > dist[now]) { continue; } if (now == A.size()) { break; } bool chk = true; for (int pos = 0; pos < B.size(); pos++) { if (now+pos>A.size() || B[pos] != A[now + pos]) { chk = false; break; } } int next = now + 1; int w = 1; if (dist[now]!=INF && dist[next] > dist[now] + w) { dist[next] = dist[now] + w; q.push({ -dist[next],next }); } next = now + B.size(); if (chk && dist[next] > dist[now] + w && dist[now] != INF) { dist[next] = dist[now] + w; q.push({ -dist[next],next }); } } cout << "#" << t << " " << dist[A.size()] << "\n"; } return 0; } | cs |
<정답 코드 - BFS>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | #include<iostream> #include<string> #include<queue> using namespace std; int main() { int tc; cin >> tc; for (int t = 1; t <= tc; t++) { string A = "", B = ""; cin >> A >> B; queue<int> q; vector<int> dist(10001, 0); dist[0] = 0; q.push(0); while (!q.empty()) { int now = q.front(); q.pop(); if (now == A.size()) { break; } bool chk = true; for (int pos = 0; pos < B.size(); pos++) { if (now+pos>A.size() || B[pos] != A[now + pos]) { chk = false; break; } } int next = now + 1; if (dist[next]==0) { dist[next] = dist[now] + 1; q.push(next); } next = now + B.size(); if (chk && dist[next]==0) { dist[next] = dist[now] + 1; q.push(next); } } cout << "#" << t << " " << dist[A.size()] << "\n"; } return 0; } | cs |
반응형
'알고리즘 > SW EXPERT' 카테고리의 다른 글
3499. 퍼펙트 셔플 (0) | 2018.03.04 |
---|---|
3752. Digit sum (0) | 2018.03.03 |
3752. 가능한 시험 점수 (4) | 2018.03.03 |
1494. 사랑의 카운슬러 (0) | 2018.03.03 |
1808. 지희의 고장난 계산기 (0) | 2018.03.02 |