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



문제를 잘못 이해해서 시간을 많이 낭비한 문제이다.


레지스터에 저장될 수 있는 수인 n은, 10000 미만, 0 이상의 수가 맞기는 한데, 무조건 네 자리로 이루어져 있다.


즉 123 이라고 하더라도, 그냥 123이 아니라 _123이라는 것이다. 123에 L연산을 하면 231이 되지만, _123에 L연산을 해봐야


123_ 이고, 결국 123이다.



본인처럼 잘못 이해하고 풀게 되면 시간초과에 걸리게 된다. 틀렸습니다가 아니라 시간 초과라서, 로직이 잘못되었다는 걸 아는데까지 시간이 오래 걸렸다.



마지막에, 최적의 결과를 내기 위한 연산의 흐름을 출력해야 하기 때문에, 큐에 삽입될 때마다 이전 노드와 사용된 연산을 parent 배열에 저장해준다.


parent[다음 수] = {이전 수, 사용된 연산} 이렇게 된다.


마지막에는 결국 parent[목표 수] 부터 시작해서 거꾸로 타고 올라가면서 처음 수가 나올 때까지 사용된 연산을 거꾸로 출력해주면 된다.



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
73
74
75
76
77
78
79
#pragma warning(disable :4996)
#include<iostream>
#include<queue>
#include<string>
#include<vector>
using namespace std;
 
int T, src, dst;
char cmd[4] = { 'D', 'S', 'L','R' };
pair<int, char> parent[10000];
 
bool vis[10000];//초기화 필요
queue<int> q;
void bfs() {
    vis[src] = true;
    q.push(src);
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        //cout << cur << '\n';
        if (cur == dst) return;
 
        for (int i = 0; i < 4; i++) {
            int next;
            if (cmd[i] == 'D') {
                next = 2 * cur;
                if (next > 9999) next %= 10000;
            }
            else if (cmd[i] == 'S') {
                next = cur - 1;
                if (cur == 0) next = 9999;
            }
            else if (cmd[i] == 'L') 
                next = (cur % 1000) * 10 + cur / 1000;
            
            else if (cmd[i] == 'R') 
                next = (cur % 10) * 1000 + cur / 10;
            
            if (vis[next] || next > 10000) continue;
            q.push(next);
            vis[next] = true;
            parent[next] = { cur, cmd[i] }; //next로 숫자가 변할 때 사용된 명령
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> T;
    while (T--) {
        cin >> src >> dst;
        bfs();
 
        pair<int, char> prev;
        prev = parent[dst];
        vector<char> v;
        v.push_back(prev.second);
 
        while (1) {
            //cout << prev.first << '\n';
            if (prev.first == src) break;
            prev = parent[prev.first];
            v.push_back(prev.second);
        }
        for (int i = v.size() - 1; i >= 0; i--)
            cout << v[i];
        cout << '\n';
 
        v.clear();
        for (int i = 0; i < 10000; i++)
            vis[i] = false;
        while (!q.empty()) q.pop();
    }
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1987번: 알파벳 (c++)  (0) 2019.09.01
백준 12851번: 숨바꼭질2 (C++)  (0) 2019.08.31
백준 13913번: 숨바꼭질 4 (C++)  (0) 2019.08.30
백준 3190번: 뱀 (C++)  (0) 2019.08.30
백준 1339번: 단어 수학 (C++)  (0) 2019.08.29

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



숨바꼭질 시리즈의 네 번째 문제이다. 이 문제는 최단 시간을 구해주고, 동시에 경로를 같이 출력해주면 된다.


경로를 출력하는 방법에는 여러가지가 있을 수 있겠지만, 현재 노드를 다음 노드의 부모라고 보고 parent 배열에 저장해주었다.



다만 이렇게 할 경우, 시작점과 목적지가 같은 경우에 올바른 경로를 출력할 수 없기 때문에 따로 예외 처리를 해주어야 한다.



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
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int src, dst, m[100002], dr[3] = { 0,1,2 }, dis[100002]; //-1, +1, *2
bool vis[100002];
vector<int> path;
queue<int> q;
int parent[100002];
void bfs() {
    
    q.push(src);
    dis[src]++;
    
    path.push_back(src);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (int i = 0; i < 3; i++) {
            int np;
            if (dr[i] == 0) np = cur - 1;
            else if (dr[i] == 1) np = cur + 1;
            else
                np = cur * 2;
 
            if (np < 0 || np > 100000 || dis[np] >= 0) continue;
            
            path.push_back(np);
            
            parent[np] = cur; //현재 노드를 다음 노드의 부모로 저장
            q.push(np);
            dis[np] = dis[cur] + 1;
 
        }
    }
}
 
int main(void) {
 
    cin >> src >> dst;
    for (int i = 0; i <= 100000; i++)
        dis[i] = -1;
    bfs();
    cout << dis[dst] << '\n';
    if (src == dst) cout << src; //출발지와 목적지가 같은 경우 예외 처리
    else {
        int prev = parent[dst];
        vector<int> v;
        v.push_back(dst);
        v.push_back(prev);
        while (1) {
            if (prev == src) break; //출발지가 나올 때까지 타고 올라감
            prev = parent[prev];
            v.push_back(prev);
        }
        for (int i = v.size() - 1; i >= 0; i--)
            cout << v[i] << ' ';
    }
 
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 12851번: 숨바꼭질2 (C++)  (0) 2019.08.31
백준 9019번: DSLR (C++)  (0) 2019.08.30
백준 3190번: 뱀 (C++)  (0) 2019.08.30
백준 1339번: 단어 수학 (C++)  (0) 2019.08.29
백준 1644번: 소수의 연속합 (C++)  (0) 2019.08.29

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



문제에 적힌 절차 그대로 구현해주면 된다.


중요한 포인트는, 매회 이동을 할 때, 몸길이를 늘려서 다음 칸을 확인한다는 것이다.


늘린 이후에, 사과라면 몸길이 유지, 사과가 아니라면 몸길이 감소 순서이다.



게임 시작 시간으로부터 X초가 끝난 뒤에라고 문제에서 명시된 것처럼, 초가 끝난 이후에, 방향을 바꿔준다.


가령 3초에 뱀이 회전해야 한다면, 2~3초의 이동이 끝난 이후에 방향을 바꿔주면 된다.



머리의 이동은 어렵지 않게 구현할 수 있다. 꼬리의 다음 위치를 파악하는 것이 중요한데, 머리의 회전과 꼬리의 회전이 동시에 일어나지 않기 때문에, 꼬리를 이동할 때 마다, 4방향 탐색을 해서 가장 생긴지 오래된 몸통을 파악한 이후에, 그 몸통을 새로운 꼬리로 갱신해주면 된다.



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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
typedef pair<int, int> pii;
int n, m[101][101], k, L, age[101][101];
 
int dr[4] = { 0,1,0,-1 };
int dc[4] = { 1,0,-1,0 };
struct Snake {
    pii head;
    pii tail;
    int dir;
};
queue<Snake> q;
 
int time = 0;
vector<pair<int, char > > turn;
 
void bfs(Snake s) {
    q.push(s);
    m[1][1] = 1;
    int ag = 0;
    age[1][1] = 1;
 
    while (!q.empty()) {
 
        Snake cur = q.front();
        q.pop();
 
        time++;
 
        int nr = cur.head.first + dr[cur.dir];
        int nc = cur.head.second + dc[cur.dir];
        if (nr <= 0 || nc <= 0 || nr > n || nc > n || m[nr][nc] == 1)
            return; //충돌 검사
 
        if (m[nr][nc] == 4) { //머리 늘려서 이동했는데 사과인 경우
            m[nr][nc] = 1;
            age[nr][nc] = 1; //나중에 꼬리 갱신할 때, 가장 오래된 몸통을 꼬리로 하기 위함
        }
        else {
            m[nr][nc] = 1;
            age[nr][nc] = 1;
            //사과 아니면 꼬리 이동
 
            pii pos;
            int maxAge = 0;
            for (int j = 0; j < 4; j++) {
 
                int tnr = cur.tail.first + dr[j];
                int tnc = cur.tail.second + dc[j];
                if (tnr <= 0 || tnc <= 0 || tnr > n || tnc > n || age[tnr][tnc] == 0) continue;
 
                if (age[tnr][tnc] > maxAge) {
                    maxAge = age[tnr][tnc];
                    pos = { tnr, tnc }; //가장 오래된 몸통
                }
            }
            m[cur.tail.first][cur.tail.second] = 0; //꼬리 제거
            age[cur.tail.first][cur.tail.second] = 0;
            cur.tail.first = pos.first; //새로운 꼬리
            cur.tail.second = pos.second;
            m[nr][nc] = 1; //다음 머리의 위치가 직전 꼬리의 위치였을 경우
            age[nr][nc] = 1;
        }
        cur.head.first = nr;
        cur.head.second = nc;
 
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (age[i][j] > 0) age[i][j]++; //전체 몸통 나이 증가
 
 
        //초 끝나고 방향 전환
        for (int i = 0; i < turn.size(); i++) {
 
            if (turn[i].first == time) {
                if (turn[i].second == 'L') {
                    cur.dir = (cur.dir + 3) % 4;
                    break;
                }//왼쪽으로 90도
                else {
                    cur.dir = (cur.dir + 1) % 4;
                    break;
                }//오른쪽 90
            }
        }
        q.push(cur);
 
    }
}
int main(void) {
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        int r, c;
        cin >> r >> c;
        m[r][c] = 4; //사과
    }
 
    cin >> L;
    for (int i = 0; i < L; i++) {
        int sec;
        char d;
        cin >> sec >> d;
        turn.push_back({ sec, d });
    }
 
    Snake snake;
    snake.head = { 1, 1 };
    snake.tail = { 1, 1 };
 
    snake.dir = 0;
    bfs(snake);
    cout << time;
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 9019번: DSLR (C++)  (0) 2019.08.30
백준 13913번: 숨바꼭질 4 (C++)  (0) 2019.08.30
백준 1339번: 단어 수학 (C++)  (0) 2019.08.29
백준 1644번: 소수의 연속합 (C++)  (0) 2019.08.29
백준 2003번: 수들의 합 2 (C++)  (0) 2019.08.29

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



순열로 풀게 되면 시간 초과가 날 것이고, 다른 방법이 필요하다.



ABC 이런 문자열이 있으면, C에는 1의 가중치를, B에는 10의 가중치를, A에는 100의 가중치를 준다. 


마찬가지로 또 다른 문자열 AR이 있다고 하면, A에는 10의 가중치를, R에는 1의 가중치를 준다.


그렇다면 전체 가중치는 A에 110, B에 10, C에 1 R에 1일 것이다. 이를 가중치 내림차순으로 사용된 알파벳만 골라서


110 * 9 + 10 * 8 + 1 * 7 + 1 * 6 이렇게 계산해주면 된다. 


즉 높은 가중치에서부터 9부터 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
#pragma warning(disable :4996)
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
 
int cnt[26], n;
 
bool cmp(int a, int b) {
    return a > b;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
 
    vector<string> wrd;
    for (int i = 0; i < n; i++) {
        string tmp;
        cin >> tmp;
        wrd.push_back(tmp);
    }
 
    
    for (int i = 0; i < wrd.size(); i++) {
        int val = 1; //가중치
        for (int j = wrd[i].length()-1; j >= 0; j--) { //문자열 우측부터 읽음
            cnt[wrd[i][j] - 'A'] += val; 
            val *= 10; // 좌측(자리수가 커지는 방향) 갈 때마다  
        }
    }
    
    vector<int> usedAlpha; 
    for (int i = 0; i < 26; i++) 
        if (cnt[i] > 0) //사용된 문자
            usedAlpha.push_back(cnt[i]);//사용된 문자만 벡터에 담음
    
    sort(usedAlpha.begin(), usedAlpha.end(), cmp); //가중치 내림차순으로 정렬
    
    ll ans = 0; int num = 9;
    for (int i = 0; i < usedAlpha.size(); i++)
        ans += usedAlpha[i] * num--; //가중치 큰 알파벳부터 9씩 곱해서 더해주면 됨
 
    cout << ans;
 
    return 0;
}
 
cs



저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 13913번: 숨바꼭질 4 (C++)  (0) 2019.08.30
백준 3190번: 뱀 (C++)  (0) 2019.08.30
백준 1644번: 소수의 연속합 (C++)  (0) 2019.08.29
백준 2003번: 수들의 합 2 (C++)  (0) 2019.08.29
백준 13458번: 시험 감독 (C++)  (0) 2019.08.29

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


n이하의 소수를 모두 구해놓고 투포인터를 적용해주면 된다.


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
#include<iostream>
#include<vector>
using namespace std;
int n, prime[4000000], num = 1;
 
void findPrime() {
    prime[0] = 2;
    
    for (int i = 3; i <= n; i++) {
        bool isPrime = true;
        for (int j = 2; j*j <= i; j++) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }    
        }
        if (isPrime) prime[num++] = i;
    }
}
int main(void) {
    cin >> n;
    findPrime();
    
    int cnt = 0, low = 0, high = 0;
    long long Sum = prime[0];
    while (1) {
        if (high >= num) break;
        
        if (Sum < n) {
            Sum += prime[++high];
        }
        else if (Sum == n) {
            cnt++;
            Sum += prime[++high];
        }
        else {
            Sum -= prime[low++];
            if (low > high) {
                if (prime[high] >= n) break;
                else {
                    high = low;
                    Sum = prime[high];
                }
            }
        }
    }
    cout << cnt;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 3190번: 뱀 (C++)  (0) 2019.08.30
백준 1339번: 단어 수학 (C++)  (0) 2019.08.29
백준 2003번: 수들의 합 2 (C++)  (0) 2019.08.29
백준 13458번: 시험 감독 (C++)  (0) 2019.08.29
백준 14500번: 테트로미노 (C++)  (0) 2019.08.29

+ Recent posts

티스토리툴바