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



백트래킹을 활용하면 풀리는 문제이다.


현재 DFS에서 거쳐온 지점들을 방문처리, 그리고 그 지점을 거쳐오면서 사용된 문자를 사용처리 해주면서 백트래킹을 진행해주면 된다.


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
#pragma warning(disable :4996)
#include<iostream>
#include<string>
using namespace std;
const int dr[4] = { 0,0,1,-1 };
const int dc[4] = { 1,-1,0,0 };
typedef pair<int, int> pii;
int row, col, Max = 0;
char m[21][21], arr[100];
bool vis[21][21], used[26];
void Print() {
    cout << '\n';
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            cout << m[i][j] << ' ';
        }
        cout << '\n';
    }
    cout << '\n';
}
 
void dfs(pii here, int k) { //지금까지 k개 지나옴
    
    if (Max < k) Max = k; 
    for (int i = 0; i < 4; i++) {
        int nr = here.first + dr[i];
        int nc = here.second + dc[i];
        if (nr < 1 || nc < 1 || nr > row || nc > col) continue;
        
        if (!used[m[nr][nc] - 'A'] && !vis[nr][nc]) { //그 문자를 안 썼고 그 지점을 거쳐 오지 않았으면
            used[m[nr][nc] - 'A'] = true; //해당 문자 사용중 
            vis[nr][nc] = true; //방문
            arr[k] = m[nr][nc];
            dfs({ nr, nc }, k + 1);
            vis[nr][nc] = false;
            used[m[nr][nc] - 'A'] = false;
        }
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> row >> col;
    for (int i = 1; i <= row; i++) {
        string input;
        cin >> input;
        for (int j = 0; j < col; j++) 
            m[i][j+1] = input[j];
    }
 
    used[m[1][1] - 'A'] = true; //시작점은 항상 사용중
    vis[1][1] = true; //항상 방문중
    dfs({ 1, 1 }, 1);
    cout << Max;
    return 0;
}
 
cs


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

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

백준 1600번: 말이 되고픈 원숭이 (C++)  (0) 2019.09.06
백준 5397번: 키로거 (C++)  (0) 2019.09.02
백준 12851번: 숨바꼭질2 (C++)  (0) 2019.08.31
백준 9019번: DSLR (C++)  (0) 2019.08.30
백준 13913번: 숨바꼭질 4 (C++)  (0) 2019.08.30

배열에서, 특정 원소의 개수를 파악하는 것을 upper_bound 그리고 lower_bound를 활용해서 할 수 있다.


1
2
3
4
5
6
7
8
9
10
sort(x.begin(), x.end());
 
    vector<ll>::iterator low, high;
    for (int i = 0; i < x.size(); i++) {
        if (mp.find(x[i]) == mp.end()) {
            low = lower_bound(x.begin(), x.end(), x[i]);
            high = upper_bound(x.begin(), x.end(), x[i]);
            mp.insert({ x[i], high - low });
        }
    }
cs



당연하게도 두 bound의 특징을 활용해서 특정 원소의 개수를 파악하기 위해서는 정렬이 필수적이다.


위 코드의 경우, low에는 처음으로 벡터의 원소가 x[i] 이상이 되는 원소의 iterator가 반환되고,


high에는 벡터의 원소중, 처음으로 x[i] 초과가 되는 원소의 iterator가 저장된다.



이때 high 혹은 low에서 x.begin()을 빼주면 몇번째 위치인지를 파악할 수 있는 것이고,


이 과정을 생략하고 high와 low의 차이를 구하면, 두 iterator의 위치 차이를 구할 수 있기 때문에, x[i]의 개수가 구해지는 것이다.



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

'Programming Language > C++' 카테고리의 다른 글

STL list insert, erase (C++)  (1) 2019.09.02
string 대소문자 변환  (0) 2019.08.25
priority_queue  (0) 2019.08.14
(C++) abs 함수의 사용  (0) 2019.08.07
(C++) list STL 출력 및 iterator  (0) 2019.08.04

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



특정 위치까지 이동할 때 최소 비용을 구해주고, 최소 비용으로 그 위치까지 도달하는 방법의 수를 구해주면 된다.


처음에는 목적지만 중복해서 방문할 수 있도록 해주면 된다고 생각했는데, 이렇게 접근하게 되면


1 -> 2로 가는경우 1+1 로 2로 가는 경우와, 1 * 2로 2로 가는 경우를 모두 잡아낼 수 있지만,


1 -> 4로 가는 경우를 생각해보면 1+1 -> 2, 2 *2 - > 4 로 가는 경우에서 2를 방문 처리한 이후에 재방문을 허용하지 않기 때문에 문제가 된다.


따라서 재방문을 목적지가 아니더라도 허용해주어야 하는데, 당연히 모든 경우에 허용해주면 안되고, 이전에 방문했을 때의 비용과 같은 경우에만 허용해주면 된다.


당연하게도 이전에 방문했던 비용보다 작은 비용으로 재방문하는 경우는 나오지 않는다.



즉, 목적지가 아닌 지점을 재방문 할 때에는, 이미 설정되어 있는 그 지점으로 이동하는 비용과, 현재 지점 + 1 을 비교해서, 같은 경우에는 재방문을 허용한다(큐에 삽입).



목적지인 지점을 재방문 할 경우에는, 위와 같이 비용 비교를 해주고, 동일 비용으로 재방문하는 경우 카운트를 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
#pragma warning(disable :4996)
#include<iostream>
#include<queue>
using namespace std;
int m[100001], src, dst, dis[100001];
const int d[3] = { 0,1,2 };
queue<int> q;
int cnt = 1; //무조건 한 가지 방법은 나온다
void bfs() {
    q.push(src);
    dis[src]++;
    while (!q.empty()) {
        int qs = q.size();
        for (int t = 0; t < qs; t++) {
            int cur = q.front();
            q.pop();
            
            int np;
            for (int i = 0; i < 3; i++) {
                if (d[i] == 0)
                    np = cur + 1;
                else if (d[i] == 1)
                    np = cur - 1;
                else
                    np = cur * 2;
                if (np < 0 || np > 100000) continue; 
                
                //이전에 방문한 적이 있더라도, 동일 비용으로 방문이 가능한 경우
                if (dis[cur] + 1 == dis[np] && dis[np] >= 0){ 
                    if (np == dst) { //목적지인 경우, 그 이후를 탐색할 필요가 없으므로 push 하지 않음
                        cnt++;
                        continue;
                    }
                    else { //이전에 방문한 곳을 여러 방법으로 거쳐갈 수 있으므로 push
                        q.push(np);
                        continue;
                    }
                    
                    //_sleep(500);
                }
 
                //위의 경우를 제외하고 비용이 양수인 경우는, 최소 비용으로 방문하는 경우가 아님
                if (dis[np] >= 0) continue; 
 
                //방문하지 않은 곳을 방문해줌
                dis[np] = dis[cur] + 1;
                q.push(np);
            }
        }
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> src >> dst;
    for (int i = 0; i <= 100000; i++)
        dis[i] = -1;
    bfs();
    
    cout << dis[dst] << '\n' << cnt;
    
    return 0;
}
 
cs


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

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

백준 5397번: 키로거 (C++)  (0) 2019.09.02
백준 1987번: 알파벳 (c++)  (0) 2019.09.01
백준 9019번: DSLR (C++)  (0) 2019.08.30
백준 13913번: 숨바꼭질 4 (C++)  (0) 2019.08.30
백준 3190번: 뱀 (C++)  (0) 2019.08.30

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



통 A가 비었을때, C에 존재할 수 있는 모든 물의 양의 경우를 출력해주면 된다.


물이 이동할 수 있는 방법은 6가지이다.


a->b, b->c ... 


초기에 각 통의 물의양은 0,0,C 이고, 6가지 모든 경우를 큐에 삽입해주고, a가 0인 순간에만 c의 물의 양을 기록해서 마지막에 출력해주면 된다.


보통 bfs문제를 풀이할 때는 큐에 삽입하는 순간에 방문처리를 해주는데, 이 문제에서는 그렇게 하면 상당히 귀찮아진다.



경우에 따라 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
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
#pragma warning(disable :4996)
#include<iostream>
#include<queue>
using namespace std;
struct Info {
    int a, b, c; //a b c 물통의 현재 물의 양
};
queue<Info> q;
bool cVis[201], abVis[201][201]; 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int A, B, C;
    cin >> A >> B >> C; //통의 부피
 
    q.push({ 0, 0, C }); //초기 물은 C에만 가득있음
    //abVis[0][0] = true;
    //cVis[C] = true;
 
    while (!q.empty()) {
        Info cur = q.front(); //현재상태
        q.pop();
        
        //printf("%d %d %d\n", cur.a, cur.b, cur.c);
        
        if (abVis[cur.a][cur.b]) continue;
 
        abVis[cur.a][cur.b] = true;
 
        if (cur.a == 0) {
            cVis[cur.c] = true;
            //printf("%d 추가\n", cur.c);
        }
 
        // a->b
        if (cur.a + cur.b > B) {
            q.push({ cur.a - (B - cur.b), B, cur.c });
            //abVis[cur.a - (B - cur.b)][B] = true;
        }
        else {
            q.push({ 0, cur.a+cur.b, cur.c });
            //abVis[0][cur.a + cur.b] = true;
        }
        // b -> a
        if (cur.b + cur.a > A) {
            q.push({ A, cur.b-(A-cur.a), cur.c });
            //abVis[A][cur.b - (A - cur.a)] = true;
        }
        else {
            q.push({ cur.a + cur.b, 0, cur.c });
            //abVis[cur.a + cur.b][0] = true;
        }
 
        // b->c
        if (cur.b + cur.c > C) {
            q.push({ cur.a, cur.b - (C - cur.c), C });
            //abVis[cur.a][cur.b - (C - cur.c)] = true;
        }
        else {
            q.push({ cur.a, 0, cur.b + cur.c });
        //    abVis[cur.a][0] = true;
        }
 
        //c->b
        if (cur.b + cur.c > B) {
            q.push({cur.a, B, cur.c-(B-cur.b) });
            //abVis[cur.a][B] = true;
        }
        else {
            q.push({ cur.a, cur.b + cur.c, 0 });
            //abVis[cur.a][cur.b + cur.c] = true;
        }
 
        //c->a
        if (cur.c + cur.a > A) {
            q.push({A, cur.b, cur.c-(A-cur.a) });
            //abVis[A][cur.b] = true;
        }
        else {
            q.push({ cur.a + cur.c, cur.b, 0 });
        //    abVis[A][cur.b] = true;
        }
 
        //a->c
        if (cur.c + cur.a > C) {
            q.push({ cur.a-(C-cur.c), cur.b, C });
            //abVis[cur.a - (C - cur.c)][cur.b] = true;
        }
        else {
            q.push({ 0, cur.b, cur.a + cur.c });
            //abVis[0][cur.b] = true;
        }
 
    }
 
    for (int i = 0; i <= C; i++)
        if (cVis[i]) cout << i << ' ';
 
    return 0;
}
 
cs


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

'알고리즘 문제 풀이 > 오답' 카테고리의 다른 글

[오답] SWEA 4008: 숫자 만들기  (0) 2019.10.08
백준 1525번: 퍼즐 (C++)  (0) 2019.08.30
연산자 우선 순위가 없는 경우 +, -, * 연산 구현  (0) 2019.08.21
[오답] 카카오 2018 블라인드 테스트: 무지의 먹방 라이브 C++  (0) 2019.08.20
[오답] 백준 1941 소문난 칠공주 C++  (0) 2019.08.10

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



2차원 배열을 문자열로 맵핑해서 해결한다.



1 2 3

4 5 6

7 8 0 


위와 같은 2차원 배열이라면 "123456780" 이러한 문자열이 되는 것이다.


0의 인덱스로부터 2차원 배열에서 0의 위치를 알아낼 수 있다.



한번의 시행에서, 빈칸의 위치를 옮길 수 있는 위치를 찾아준 다음에, 이전 시행에서 찾은 경우만큼만 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
66
67
68
69
70
71
#include<iostream>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
 
const int dzero[4] = { -3, 3, -1, 1 }; //상하좌우
const int dr[4] = { -1,1,0,0 };
const int dc[4] = { 0,0,-1, 1 };
 
int main(void) {
    string str ="", dst = "123456780";
    
    for (int i = 0; i < 9; i++) {
        int input;
        cin >> input;
        str += input + '0';
    }
    
    set<string> vis;
    vis.insert(str);
    
    queue<string> q;
    q.push(str);
    int cnt = 0;
    
    while(!q.empty()) {
        int qSize = q.size(); //이전 시행에 찾았던 0이 이동 가능한 경우만 실행
        for (int i = 0; i <qSize; i++) {
            string cur = q.front(); //현재 문자열
            q.pop();
 
            if (cur == dst) { //목적 문자랑 같으면 종료
                cout << cnt;
                return 0;
            }
            //cnt++;
 
            int zeroPos=0; //0위치 검색
            for (int j = 0; j < cur.length(); j++) {
                if (cur[j] == '0') {
                    zeroPos = j;
                    break;
                }    
            }
            
            //문자열의 0의 위치로부터 2차원 배열에서의 위치를 맵핑
            int zeroR = zeroPos / 3;
            int zeroC = zeroPos % 3;
 
            for (int j = 0; j < 4; j++) { //0이 움직일 수 있는 방향을 찾음
                int nr = zeroR + dr[j];
                int nc = zeroC + dc[j];
                if (nr < 0 || nc < 0 || nr >= 3 || nc >= 3) continue;
                
                string next = cur;
                swap(next[zeroPos], next[zeroPos + dzero[j]]);
 
                if (vis.find(next) == vis.end()){
                    vis.insert(next);
                    q.push(next);
                }
            }
        }
        cnt++; //이전에 찾은 경우들 다 해보고 
    }
    cout << -1;
    return 0;
}
 
cs



참고: http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220438835865

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

'알고리즘 문제 풀이 > 오답' 카테고리의 다른 글

[오답] SWEA 4008: 숫자 만들기  (0) 2019.10.08
백준 2251번: 물통 (C++)  (0) 2019.08.31
연산자 우선 순위가 없는 경우 +, -, * 연산 구현  (0) 2019.08.21
[오답] 카카오 2018 블라인드 테스트: 무지의 먹방 라이브 C++  (0) 2019.08.20
[오답] 백준 1941 소문난 칠공주 C++  (0) 2019.08.10

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

티스토리툴바