728x90

 0. [c++] 백준


https://www.acmicpc.net/problem/13913


 1. 풀이



 2. 소스코드


- 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
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int N, K;
bool visited[200001];
 
void solve() {
    queue<vector<int> > qu;
    qu.push(vector<int>(1, N));
 
    while (!qu.empty()) {
        vector<int> here = qu.front();
        int here_num = here.back();
        qu.pop();
        if (here_num == K) {
            cout << here.size() - 1 << endl;
            for (int i = 0; i < here.size(); i++)
                cout << here[i] << " ";
            return;
        }
        
        if (here_num * 2 <= K * 2 && !visited[here_num * 2]) {
            here.push_back(here_num * 2);
            qu.push(here);
            here.pop_back();
            visited[here_num * 2] = true;
        }
        
        if (here_num + 1 <= K && !visited[here_num + 1]) {
            here.push_back(here_num + 1);
            qu.push(here);
            here.pop_back();
            visited[here_num + 1] = true;
        }
 
        if (here_num > 0 && !visited[here_num - 1]) {
            here.push_back(here_num - 1);
            qu.push(here);
            here.pop_back();
            visited[here_num - 1] = true;
        }
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N >> K;
 
    solve();
}
cs



- 2차 코드(경로를 int 배열에 저장)

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
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int N, K;
bool visited[200001];
int path[200001];
 
void solve() {
    queue<pair<int, int> > qu;
    qu.push({ N,0 });
 
    while (!qu.empty()) {
        pair<int, int> here = qu.front();
        qu.pop();
 
        if (here.first == K) {
            cout << here.second << endl;
            vector<int> ans;
            int count = here.second;
            int next = K;
            ans.push_back(K);
            while (count--) {
                ans.push_back(path[next]);
                next = path[next];
            }
            reverse(ans.begin(), ans.end());
 
            for (int i = 0; i < ans.size(); i++) {
                cout << ans[i] << " ";
            }
            return;
        }
        
        if (here.first * 2 <= K * 2 && !visited[here.first * 2]) {
            qu.push({ here.first * 2, here.second + 1 });
            visited[here.first * 2] = true;
            path[here.first * 2] = here.first;
        }
        
        if (here.first + 1 <= K && !visited[here.first + 1]) {
            qu.push({ here.first + 1, here.second + 1 });
            visited[here.first + 1] = true;
            path[here.first + 1] = here.first;
        }
 
        if (here.first > 0 && !visited[here.first - 1]) {
            qu.push({ here.first - 1, here.second + 1 });
            visited[here.first - 1] = true;
            path[here.first - 1] = here.first;
        }
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N >> K;
 
    solve();
}
cs


 3. 참고




질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!


저작자표시

'<백준> > 동적 계획법' 카테고리의 다른 글

[c++]백준 9019 - DSLR (DP)  (0) 2020.04.18
[c++] 백준 2618 - 경찰차(dp)  (0) 2020.04.18
[c++] 백준 14003 - 가장 긴 증가하는 부분 수열 5(dp)  (0) 2020.04.17
[c++] 백준 14002 - 가장 긴 증가하는 부분 수열4(dp)  (0) 2020.04.17
[c++] 백준 12852 - 1로 만들기 2(dp)  (0) 2020.04.17

+ Recent posts

티스토리툴바