https://programmers.co.kr/learn/courses/30/lessons/12916



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <string>
#include <iostream>
#include<algorithm>
using namespace std;
 
int cnt[2];
bool solution(string s)
{
    transform(s.begin(), s.end(), s.begin(), ::tolower);
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'p') cnt[0]++;
        else if (s[i] == 'y') cnt[1]++;
    }
    if (cnt[0== cnt[1]) return 1;
    else return 0;
 
}
cs


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



설명은 주석으로 대체한다.




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
typedef long long ll;
using namespace std;
 
ll d[91]; //i자리 이친수의 개수
int main(void) {
    
    d[1= 1// 1
    d[2= 1//10
    for (int i = 3; i <= 90; i++) {
        d[i] = 1;
        for (int j = i - 2; j >= 1; j--) {
            d[i] += d[j]; 
        }//맨앞 1두면 바로옆은 무조건 0이고, 남은 자리에 이친수를 채워준다
    }
    
    int val;
    cin >> val;
    cout << d[val];
    return 0;
}
cs



0과 1이 사용되는 횟수를 dp로 각각 표현해준다.



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
#include<iostream>
using namespace std;
 
int zero[41], one[41];
int main(void) {
    
    zero[0= 1;
    zero[1= 0;
    zero[2= 1;
    one[0= 0;
    one[1= 1;
    one[2= 1;
    
    for (int i = 3; i < 41; i++) {
        zero[i] = zero[i - 1+ zero[i - 2];
        one[i] = one[i - 1+ one[i - 2];
    }
    int n;
    cin >> n;
    while (n--) {
        int val;
        cin >> val;
        cout << zero[val] << ' ' << one[val] << '\n';
    }
    return 0;
}
cs


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



시작하는 수를 설정해둔다.


가령 5를 만드는 경우는


1 + 4를 만드는 경우

2 + 3을 만드는 경우

3 + 2를 만드는 경우


이렇게 볼 수 있다.


arr[i] = 1,2,3을 사용해서 합 i를 만드는 방법의 수라고 한다면



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
 
using namespace std;
int arr[11]; //1,2,3을 적절히 더해서 i를 만드는 방법의 수 (순서 다르면 다른 경우로 봄)
int main(void) {
    
    arr[1= 1;
    arr[2= 2;
    arr[3= 4;
 
    for (int i = 4; i <= 10; i++
        arr[i] = arr[i - 3+ arr[i - 2+ arr[i - 1];
    
    int n;
    cin >> n;
    while (n--) {
        int val;
        cin >> val;
        cout << arr[val] << '\n';
    }
    return 0;
}
cs


https://www.welcomekakao.com/learn/courses/30/lessons/42577



해시 카테고리로 분류되어 있긴 하지만, 본인이 편한 풀이로 풀면 그만이다.



본인은 전화번호들을 길이가 길어지는 순서대로 정렬하였다.


이후에 짧은 전화번호를 기준으로 그것보다 긴 전화번호들을 비교했다.




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
#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
 
bool cmp(string a, string b) {
    return a.length() < b.length();
}
bool solution(vector<string> pb) {
    sort(pb.begin(), pb.end(), cmp); //길이 짧은게 앞으로
    
    
 
    for (int i = 0; i < pb.size(); i++) {
        for (int j = i+1; j < pb.size(); j++) {
            bool isSame = true;
            for (int k = 0; k < pb[i].length(); k++) {
                if (pb[i][k] != pb[j][k]) {
                    isSame = false;
                    break;
                }
            }
            if (isSame) return false;
        }
    }
    return true;
}
 
int main(void) {
    solution({  "97674223""1195524421""119" });
    return 0;
}
 
 
cs


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


방문 처리 배열을 3차원으로 만들어 준다. 나이트처럼 이동하는 것을 점프라고 하면, 


[row][col][이 지점에서 가능한 점프 횟수]


위와 같이 설정해준다.



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
#include<iostream>
#include<queue>
 
using namespace std;
int map[201][201], row, col, k;
bool  vis[201][201][31]; //r, c, 점프 가능 횟수
struct Info {
    int r, c, jump, cnt;
};
 
queue<Info> q;
const int dr[4= { 0,0,1,-1 };
const int dc[4= { 1,-1,0,0 };
const int jr[8= { -2,-1,1,2,2,1,-1,-2 };
const int jc[8= { 1,2,2,1,-1,-2,-2,-1 };

void bfs() {
    q.push({ 00, k, 0 });
    vis[0][0][k] = true;
    while (!q.empty()) {
        int qs = q.size();
        while (qs--) {
            
            Info cur = q.front();
            q.pop();
            if (cur.r == row - 1 && cur.c == col - 1) {
                cout << cur.cnt;
                return;
            }
            for (int i = 0; i < 4; i++) {
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];
                if (nr < 0 || nc < 0 || nr >= row || nc >= col || map[nr][nc] == 1continue;
                
                if (vis[nr][nc][cur.jump]) continue//z만큼 점프 개수를 남기고 온적이 있으면 pass
                q.push({ nr, nc, cur.jump, cur.cnt + 1 });
                vis[nr][nc][cur.jump] = true;
                
            }
 
            if (cur.jump <= 0continue;
            for (int i = 0; i < 8 ; i++) {
                int nr = cur.r + jr[i];
                int nc = cur.c + jc[i];
                if (nr < 0 || nc < 0 || nr >= row || nc >= col || map[nr][nc] == 1continue;
                
                if (vis[nr][nc][cur.jump - 1]) continue//z만큼 점프 개수를 남기고 온적이 있으면 pass
                q.push({ nr, nc, cur.jump - 1, cur.cnt + 1 });
                vis[nr][nc][cur.jump - 1= true;
            }
 
        }
    }
    cout << -1;
}
 
int main(void) {
    cin >> k >> col >> row;
    for (int i = 0; i < row; i++
        for (int j = 0; j < col; j++
            cin >> map[i][j];
            
    bfs();
 
    return 0;
}
cs


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



여러가지 풀이가 가능하겠지만, 링크드리스트를 활용해서 풀었다.



STL list의 여러가지 함수들을 자유롭게 활용할 줄 안다면 무리 없이 풀리는 문제이다.



커서의 초점을 삽입에 맞추느냐 삭제에 맞추느냐에 따라서 풀이가 약간씩은 달라질 수 있겠다.



즉  a b c 이러한 문자열 상황에서, 커서가 a에 있는 상태에서, 삽입 명령이 들어오면 a 왼편에 새로운 문자가 들어가야 하고


삭제 명령이 들어오면 아무런 변화도 일어나지 않아야 한다.


하지만 실제 구현을 할 때, iterator를 .begin()에 두고 삭제를 하게 되면 a가 삭제될 것이다.


즉 삭제의 경우에는, 커서의 왼편에 있는 값을 삭제해주도록 구현을 해야한다.



정리하면, iterator의 위치를 insert의 인자로 활용하는 경우에, 삭제를 구현하려면 한 칸 왼쪽의 값을 삭제해주어야 한다.




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
#include<iostream>
#include<list>
#include<string>
using namespace std;
//list insert할 때, itr이 가리키는 왼편에 새로운 수 삽입, itr은 원래 가리키던 수를 가리킴
//erase: itr이 가리키던 수 지워버리고, 우측에 있는 수를 가리킴
int main(void) {
    int T;
    cin >> T;
    while (T--) {
        string str;
        cin >> str;
        list<char> ans;
 
        
        list<char>::iterator itr = ans.end(); //커서의 초기 위치
        
        for (int i = 0; i < str.length(); i++) {
            
            if (str[i] == '<') {
                if (itr == ans.begin()) continue;
                itr--;
            }
            else if (str[i] == '>') {
                if (itr == ans.end()) continue;
                itr++;
            }
            else if (str[i] == '-') {
                if (itr == ans.begin()) continue;
                itr = ans.erase(--itr); //erase 시에는 반환되는 itr을 받아서 갱신해줘야 한다
            }
            else {
                ans.insert(itr, str[i]);
            }
        }
 
        //print
        for (auto it = ans.begin(); it != ans.end(); it++
            cout << *it;
        cout << '\n';
        ans.clear();
    }
    return 0;
}
 
 
cs

 

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<intint> 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({ 11 }, 1);
    cout << Max;
    return 0;
}
 
cs


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 > 100000continue
                
                //이전에 방문한 적이 있더라도, 동일 비용으로 방문이 가능한 경우
                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] >= 0continue
 
                //방문하지 않은 곳을 방문해줌
                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


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({ 00, 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


+ Recent posts