본문 바로가기

알고리즘/SW EXPERT

3143. 가장 빠른 문자열 타이핑

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(100010);
        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