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

 

1717번: 집합의 표현

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는

www.acmicpc.net

 

전형적인 Union-Find 문제이다. 또는 분리 집합 유형이라고 불린다.

 

n이 포함된 집합을 나타내는 정수 배열로 r[n]을 사용하자.

 

먼저 0부터 n까지, r[n]을 자기 자신으로 초기화한다.

 

그리고 주어지는 명령에 따라서 union과 find를 구현한다.

 

0, a, b가 주어지면 a가 속한 곳을 b가 속한 곳으로 수정해준다.

 

가령, a가 속한 집합이 3이고, 3이 속한 집합이 2라면 r[3]이 b가 속한 집합으로 수정되어야 하기 때문에,

r[getParent(a)] = getParent(b) 의 로직을 사용한다.

 

getParent의 경우, r[n]=n이 나올 때까지, 즉 최상단 부모노드일 때까지 getParent가 실행되어야 한다.

 

#include<iostream>
using namespace std;

int r[1000001];
int n, m;

int getParent(int num) { //find
	if (r[num] == num)
		return num;
	else{
		return r[num] = getParent(r[num]);
	}
}

void join(int a, int b) { // union
	//a의 부모를 b의 부모로 수정
	r[getParent(a)] = getParent(b);



int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;

	for (int i = 0; i <= n; i++) {
		r[i] = i;
	}

	while (m--) {
		int cmd, a, b;
		cin >> cmd >> a >> b;

		if (cmd == 0) {
			join(a, b);
		}
		else {
			if (getParent(a) == getParent(b))
				cout << "YES\n";
			else
				cout << "NO\n";
		}
	}

	return 0;
}
저작자표시 비영리 변경금지

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

백준 17472번: 다리만들기2 (C++)  (0) 2019.10.19
백준 17471번: 게리맨더링 (C++)  (0) 2019.10.02
백준 13549번: 숨바꼭질 3 (C++)  (0) 2019.09.27
백준 3055번: 탈출 (C++)  (0) 2019.09.27
백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26

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




1. 섬마다 인덱스를 부여한다. (각각의 섬들을 구분한다.)


2. 모든 경우에 다리를 놓아본다.

다리를 놓을 수 있는 조건에 맞춰서(길이 2이상)


3. 당연하게도 모든 섬을 최소의 간선으로 연결하는 경우, 간선의 수는 섬의 수 - 1이다.


하지만 다리마다 비용이 다 다르기 때문에, 많은 다리를 적은 비용을 놓고 연결하는 경우가 있을 것이다.


따라서 찾은 다리의 수가 k개라고 하고, 섬의 개수를 N개라고 한다면,



찾은 다리 k개 중에 (N-1개~K개)를 뽑아보고, 섬의 연결상태를 확인해서 모든 섬을 연결할 수 있는 경우에 답을 업데이트 해준다.




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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include<iostream>
#include<queue>
#define INF 987654321
 
using namespace std;
typedef pair<int, int> pii;
const int dr[4] = { 0,0,1,-1 };
const int dc[4] = { 1,-1,0,0 };
 
struct Info{
    int isl = -1;
    int val = 0;
};
 
struct Bridge {
    int src, dst, len;
};
 
vector<Bridge> v;
 
Info m[101][101];
int R, C, islCnt = 0;
 
queue<pii> q;
bool vis[101][101];
 
int brg[7][7]; //다리 길이 정보
 
int st = 0;
bool used[40];
int arr[100]; //뽑는다리
int ans = INF;
 
bool vis2[7];
 
int map[7][7];
 
queue<int> q2;
 
void bfs(pii st) { //섬 번호 매기는 용도
    q.push(st);
    vis[st.first][st.second] = true;
    m[st.first][st.second].isl = islCnt;
    while (!q.empty()) {
        pii cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            
            if (nr < 0 || nc < 0 || nr >= R || nc >= C || vis[nr][nc]) continue;
            if (m[nr][nc].val == 0) continue;
            
            q.push({ nr, nc });
            vis[nr][nc] = true;
            m[nr][nc].isl = islCnt;
        }
    }
}
 
void bfsCon(int st) { //다리 골랐을 때 연결 관계 확인
    q2.push(st);
    vis2[st] = true;
    while (!q2.empty()) {
        int cur = q2.front();
        q2.pop();
        for (int i = 0; i < islCnt; i++) {
            if (map[cur][i] == 0) 
                continue;
            if (vis2[i]) 
                continue;
            q2.push(i);
            vis2[i] = true;
            
        }
    }
}
 
void btk(int k, int goal) {
    if (k == goal) {
    
        int len = 0;
        for (int i = 0; i < k; i++) {
            Bridge b = v[arr[i]];
            map[b.src][b.dst] = b.len;
            map[b.dst][b.src] = b.len;
            len += b.len;
        }
 
    
        bool isBreak = false;
        for (int i = 0; i < islCnt; i++) {
            for (int j = 0; j < islCnt; j++) {
                if (i == j) continue;
                if (map[i][j] != 0) {
                    bfsCon(i);
                    isBreak = true;
                    break;
                }
 
            }
            if (isBreak) break; //연결 관계 확인은 딱 한 번만
        }
        
        bool suc = true;
        for (int i = 0; i < islCnt; i++) {
            if (!vis2[i]) //실패
                suc = false;
 
            vis2[i] = false; //초기화
            for (int j = 0; j < islCnt; j++) 
                map[i][j] = 0;
            
        }
 
        if (suc) 
            if (ans > len) ans = len;
            
        return;
    }
 
    if (k == 0) st = 0;
    for (int i = st; i < v.size(); i++) {
        if (!used[i]) {
            st = i;
            used[i] = true;
            arr[k] = i;
            btk(k + 1, goal);
            used[i] = false;
        }
    }
}
 
int main(void) {
    //setbuf(stdout, NULL);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    //땅이나오면 이 땅에서 길이 2 이상의 다리로 연결가능한 섬 찾아서
    //그 땅이 속한 섬에서 연결할 수 있는 곳에 추가
    //v[k].pushback n  -> k번 섬에서 n번섬에 갈 수 있다. 길이 몇으로
    
    cin >> R >> C;
    for (int i = 0; i < R; i++) 
        for (int j = 0; j < C; j++) 
            cin >> m[i][j].val;
        
    
 
    //섬 번호 부여
    for (int i = 0; i < R; i++) 
        for (int j = 0; j < C; j++) 
            if (m[i][j].val == 1 && !vis[i][j]) {
                bfs({ i, j });
                islCnt++;
            }
        
    //다리 길이 무한대로 초기화
    for (int i = 0; i < islCnt; i++) 
        for (int j = 0; j < islCnt; j++) 
            brg[i][j] = INF;
        
    
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (m[i][j].val == 0) continue;
            //바다는 pass
            
            for (int k = 0; k < 4; k++) { //4방향으로 다리 놔보기
                //범위 벗어나면 다른 경우
                // 1이면서 나랑 다른 섬이어야 다리에 추가
 
                for (int p = 1; p < 101; p++) {
                    int nr = i + dr[k] * p;
                    int nc = j + dc[k] * p;
                    if (nr < 0 || nc < 0 || nr >= R || nc >= C || (m[nr][nc].isl == m[i][j].isl)) break;
                    if (m[nr][nc].val == 1 && p <= 2) break; //길이 1 이하인 다리
                    if (m[nr][nc].val == 1 && (m[nr][nc].isl != m[i][j].isl) && p >= 3) {
                        //p-1이 다리길이
                        if (brg[m[nr][nc].isl][m[i][j].isl] > p - 1) {
                            brg[m[nr][nc].isl][m[i][j].isl] = p - 1;
                            brg[m[i][j].isl][m[nr][nc].isl] = p - 1;
                        }
                        break;
                    }
                }
            }
        }
    }
 
    
    for (int i = 0; i < islCnt; i++) 
        for (int j = i; j < islCnt; j++) 
            if (brg[i][j] != INF) 
                v.push_back({ i, j, brg[i][j]}); //다리 정보
    
    for (int i = islCnt - 1; i <= v.size(); i++) //최소 섬개수-1개의 다리로 연결 or 모든 다리 사용
        btk(0, i);
    
 
    if (ans == INF) cout << -1;
    else cout << ans;
 
    return 0;
}
 
cs


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

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

백준 1717번: 집합의 표현(C++)  (0) 2021.10.06
백준 17471번: 게리맨더링 (C++)  (0) 2019.10.02
백준 13549번: 숨바꼭질 3 (C++)  (0) 2019.09.27
백준 3055번: 탈출 (C++)  (0) 2019.09.27
백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26

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



선거구가 형성될 수 있는 조건은 선거구에 구역이 1개 이상 포함되는 것이다.



따라서 조합을 이용해서, 주어지는 n개의 구역 중에서 1개 이상 뽑는 경우에 대해서 처리해주면 된다.


단, n개를 뽑게 되면, 다른 선거구에 속하는 구역이 0개가 된다는 의미이므로 n개 뽑는 경우는 제외해준다.




구역을 적절하게 뽑았다면 다음과 같은 처리를 해준다.


우선 n <= 10 으로 작기 때문에 2차원 bool 배열에 구역의 연결 관계를 인접행렬로 나타내준다.


그리고 처음에 뽑은 구역들이 선거구를 이룰 수 있는지(모두 연결되어 있는지) 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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
 
int n, pop[11], tot = 0, Min = 987654321, st = 1;
bool vis[11], map[11][11], used[11];
queue<int> q;
 
int bfs(int st, bool usedCheck) { //true인 경우가 처음 뽑은 구역들 연결 확인하는 경우
    q.push(st);
    vis[st] = true;
    int restSum = pop[st];
    
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (usedCheck)
                if (!used[i]) continue; //뽑은 곳들에 대해서만 연결 관계 확인
            
            if (!map[cur][i] || vis[i]) continue;
            
            q.push(i);
            vis[i] = true;
            restSum += pop[i];
        }
    }
    return restSum; //선거구 인원 반환
}
 
void process() {
    int pickedSum, restSum;
    
 
    //처음에 뽑은 게 모두 연결되어 있는지 확인
    for (int i = 1; i <= n; i++) {
        if (used[i]) {
            pickedSum = bfs(i, true);
            break;
        }
    }
 
    bool firCon = true;
    for (int i = 1; i <= n; i++) {
        if (used[i]) { //뽑은 것중에
            if (!vis[i]) firCon = false; //연결 안 된거 하나라도 있으면 거르기
        }
    }
 
    for (int i = 1; i <= n; i++) //방문 처리 배열 초기화
        vis[i] = false;
 
    if (!firCon) return;
 
 
    for (int i = 1; i <= n; i++) 
        if (used[i]) vis[i] = true; //확정된 선거구 방문처리
    
    for(int i = 1; i <= n; i++) {
        if (!vis[i]) {
            restSum = bfs(i, false); //나머지 선거구 인원 계산 + 연결 관계 확인
            break;
        }
    }
 
    bool allCon = true;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) { //선거구 형셩 불가
            allCon = false;
            break;
        }
    }
    
    if(allCon) {
        int dif = abs(tot - restSum - restSum);
        if (Min > dif) Min = dif;
    }
    for (int i = 1; i <= n; i++)
        vis[i] = false;
}
void btk(int cnt) {
    if (cnt >= 1) {
        if (cnt >= 6) return;
        //전부 다 뽑은 경우 제외
        process();
    }
    
    if (cnt == 0) st = 1;
    for (int i = st; i <= n; i++) {
        if (!used[i]) {
            st = i;
            used[i] = true;
            btk(cnt + 1);
            used[i] = false;
        }
    }
}
 
int main(void) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> pop[i];
        tot += pop[i];
    }
 
    for (int i = 1; i <= n; i++) {
        int edgeCnt;
        cin >> edgeCnt;
        while (edgeCnt--) {
            int dst;
            cin >> dst;
            map[dst][i] = true;
            map[i][dst] = true;
        }
    }
 
    btk(0);
 
    if (Min == 987654321) cout << -1;
    else
        cout << Min;
 
    return 0;
}
cs


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

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

백준 1717번: 집합의 표현(C++)  (0) 2021.10.06
백준 17472번: 다리만들기2 (C++)  (0) 2019.10.19
백준 13549번: 숨바꼭질 3 (C++)  (0) 2019.09.27
백준 3055번: 탈출 (C++)  (0) 2019.09.27
백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26

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


최단거리를 구해야하고, 간선이 음이 아니면서 모두 같은 상황이 아니기 때문에 다익스트라를 이용해야 한다.



0. 시작점에서 특정 지점까지 가는 비용(거리, 시간...) 무한대로 초기화

0. pair 자료구조의 sorting을 활용하기 위해서 {dist[], 지점} 으로 사용.

1. 시작점 pq에 push(min heap)


2. pq에서 하나 꺼내고, pop하고 꺼낸 지점 방문처리


3. 이동할 수 있는 지점 확인. 범위 밖이거나, 이미 방문한 지점이면 pass


4. 시작점에서 이동할 수 있는 지점까지의 거리 > 시작점에서 현재 지점까지 거리 + 현재 지점에서 이동할 수 있는 지점까지 가는 비용

이라면 좌변을 우변으로 갱신. pq에 push


5. 목적지를 방문처리하고, 이동이 완료되면 종료



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>
#include<functional>
#include<limits.h> //이 헤더로 해야 백준에서 돌아감
 
using namespace std;
typedef pair<int, int> pii;
 
int dis[100001], src, dst;
bool vis[100001];
priority_queue<pii, vector<pii>, greater<pii> > pq;
 
void dijk() {
    pq.push({ 0, src }); //{그 지점까지 가는 비용, 지점}
    dis[src] = 0;
 
    while (!pq.empty()) {
        int here = pq.top().second; //현재 확인하는 지점
        pq.pop();
        vis[here] = true; //방문처리
        
        int there, moveCost; //다음 방문지점, here에서 there로 가는 비용
 
        for (int i = 0; i < 3; i++) {
            //0앞으로 걷기, 1뒤로걷기, 2점프
            if (i == 0)
                there = here + 1;
            else if (i == 1) there = here - 1;
            else
                there = here * 2;
 
            if (i != 2)
                moveCost = 1;
            else
                moveCost = 0;
 
            if (there < 0 || there > 100000 || vis[there]) continue;
 
            //이미 계산된 src에서 there까지 가는 비용이
            //src~here 비용 + here~there비용보다 크면 갱신하고 pq에 삽입
            if (dis[there] > dis[here] + moveCost) { 
                dis[there] = dis[here] + moveCost;
                pq.push({ dis[there], there });
            }
        }
        if (here == dst) return; //목적지가 방문처리 되었으므로 확인 그만
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    for (int i = 0; i <= 100000; i++)
        dis[i] = INT_MAX; //무한대로 초기화
 
    cin >> src >> dst;
 
    dijk();
 
    cout << dis[dst];
    return 0;
}
 
 
cs


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

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

백준 17472번: 다리만들기2 (C++)  (0) 2019.10.19
백준 17471번: 게리맨더링 (C++)  (0) 2019.10.02
백준 3055번: 탈출 (C++)  (0) 2019.09.27
백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26
백준 1746번: 듣보잡 (C++)  (0) 2019.09.26

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



다음번에 물이 확산할 곳으로는 이동할 수 없다고 했으므로, 물의 확산을 먼저 수행해준다.


그리고 길이 1만큼 이동 가능한 경우를(특정 시점에 들어있는 큐의 크기만큼만) 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
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
#pragma warning(disable :4996)
#include<iostream>
#include<queue>
 
using namespace std;
typedef pair<int, int> pii;
const int dr[4] = { 0,0,1,-1 };
const int dc[4] = { 1,-1,0,0 };
 
int R, C;
char m[51][51];
int dis[51][51];
 
pii st;
queue<pii> q;
queue<pii> fldq;
bool fldVis[51][51];
 
void fldbfs() {
    int qs = fldq.size();
    while (qs--) { //한 번의 확산만 일어나도록
        pii cur = fldq.front();
        fldq.pop();
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            
            if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
            if (fldVis[nr][nc] || m[nr][nc] =='D' || m[nr][nc] == 'X') continue;
            m[nr][nc] = '*';
        }
    }
}
 
void flood() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (!fldVis[i][j] && m[i][j] == '*') {
                fldq.push({ i, j }); //확산 지점들 미리 push
                fldVis[i][j] = true;
            }
        }
    }
    fldbfs();
}
void bfs() {
    q.push(st);
    dis[st.first][st.second]++;
 
    while (!q.empty()) {
        int qs = q.size();
        //물이동 먼저 하고, 길이 1만큼 이동하도록
 
        flood();
        while (qs--) {
            
            pii cur = q.front();
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int nr = cur.first + dr[i];
                int nc = cur.second + dc[i];
                if (nr < 0 || nc < 0 || nr >= R || nc >= C || dis[nr][nc] >= 0)
                    continue;
                
                if (m[nr][nc] == '*' || m[nr][nc] == 'X') continue;
                
                q.push({ nr, nc });
                dis[nr][nc] = dis[cur.first][cur.second] + 1;
                
                if (m[nr][nc] == 'D') {
                    cout << dis[nr][nc];
                    return;
                }
            }
        }
    }
    
    cout << "KAKTUS";
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    //*물, X돌, 비버굴D, 고슴도치S
    
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> m[i][j];
            dis[i][j] = -1;
            if (m[i][j] == 'S') {
                st.first = i;
                st.second = j;
            }
        }
    }
 
    bfs();
    
    return 0;
}
 
 
cs


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

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

백준 17471번: 게리맨더링 (C++)  (0) 2019.10.02
백준 13549번: 숨바꼭질 3 (C++)  (0) 2019.09.27
백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26
백준 1746번: 듣보잡 (C++)  (0) 2019.09.26
백준 1032번: 명령 프롬프트 (C++)  (0) 2019.09.26

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



주어진 문자열을 처음부터 끝까지 한 번만 검사한다.


검사하면서, 폭발 단어의 마지막 철자와 같은 철자가 나오면, 현재까지 만들어둔 정답이 폭발 단어를 포함하는지 확인한다.


만약 포함한다면, 필요한 횟수만큼 pop_back 해주고, 그렇지 않으면 이어서 해당 철자를 이어서 붙여준다.



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
#include<iostream>
#include<string>
 
using namespace std;
 
string ans = "";
int main(void) {
    string str, bomb;
    cin >> str >> bomb;
    
    int k = 0; //str의 길이만큼 확인 (확인할 인덱스)
    while (k < (int)str.length()) {
 
        //단어폭탄의 마지막 문자와 같으면서, 단어 폭탄의 길이 이상의 단어가 ans 문자열에 들어 있을 때만 검사
        if (str[k] == bomb[bomb.length() - 1] && ans.length() >= bomb.length()-1) {
            bool isBomb = true;
            int idx = 0;
            for (int j = 1; j <= bomb.length()-1; j++) { //마지막 문자는 어짜피 같으니까, 제외하고 검사
                if (ans[ans.length() - bomb.length() + j] != bomb[idx]) {
                    isBomb = false;
                    break;
                }
                else
                    idx++;
            }
            if (isBomb) { //단어 폭탄인 경우 
                for (int i = 0; i < bomb.length() - 1; i++)
                    ans.pop_back();
            }
            else //폭탄검사를 했는데 아닌 경우
                ans += str[k];
        }
        else { //단어 폭탄의 마지막 철자와 글자가 달랐던 (평범한) 경우
            ans += str[k];
        }
        k++; //확인하는 문자열 위치 증가
    }
    if ((int)ans.length() != 0)
        cout << ans;
    else
        cout << "FRULA"; 
    return 0;
}
cs




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

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

백준 13549번: 숨바꼭질 3 (C++)  (0) 2019.09.27
백준 3055번: 탈출 (C++)  (0) 2019.09.27
백준 1746번: 듣보잡 (C++)  (0) 2019.09.26
백준 1032번: 명령 프롬프트 (C++)  (0) 2019.09.26
백준 2941번: 크로아티아 알파벳 (C++)  (0) 2019.09.26

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


set에 들어보지 못한 사람 저장하고, 처음 본사람 이름을 받으면서 set에 있으면 결과 벡터에 담고, 마지막에 정렬 이후 출력


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
#pragma warning(disable :4996)
#include<iostream>
#include<set>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
 
set<string> lis;
vector<string> see;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        string temp;
        cin >> temp;
        lis.insert(temp);
    }
    
    for (int i = 0; i < m; i++) {
        string temp;
        cin >> temp;
        if (lis.find(temp) != lis.end()) //lis set에 존재하면 결과에 push
            see.push_back(temp);
    }
    
    sort(see.begin(), see.end());
    cout << see.size() << '\n';
    for (int i = 0; i < see.size(); i++)
        cout << see[i] << '\n';
    
    return 0;
}
 
 
cs


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

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

백준 3055번: 탈출 (C++)  (0) 2019.09.27
백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26
백준 1032번: 명령 프롬프트 (C++)  (0) 2019.09.26
백준 2941번: 크로아티아 알파벳 (C++)  (0) 2019.09.26
백준 1316번: 그룹 단어 체커 (C++)  (0) 2019.09.25

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




문자열을 입력 받을 때마다, 달라지는 부분을 '?'로 변경해주면 된다.



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
#pragma warning(disable :4996)
#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<string> v;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    //첫 입력으로 초기화 하고, 다른 부분 ?로 다 바꾸기(이미 ?가 아닌 경우에)
    int n;
    cin >> n;
    string str;
    cin >> str;
    for (int i = 0; i < n - 1; i++) {
        string val;
        cin >> val;
        
        for (int i = 0; i < str.length(); i++) {
            if (str[i] != '?' && str[i] != val[i])
                str[i] = '?';
        }
 
    }
    cout << str;
    return 0;
}
 
 
cs


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

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

백준 9935번: 문자열 폭발 (C++)  (0) 2019.09.26
백준 1746번: 듣보잡 (C++)  (0) 2019.09.26
백준 2941번: 크로아티아 알파벳 (C++)  (0) 2019.09.26
백준 1316번: 그룹 단어 체커 (C++)  (0) 2019.09.25
백준 1157번: 단어 공부 (C++)  (0) 2019.09.25

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


주어진 경우의 수를 모두 처리해주면 된다.


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
#pragma warning(disable :4996)
#include<iostream>
#include<string>
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string str;
    cin >> str;
    
    int i = 0, cnt = 0;
    while (i < str.length()) {
 
        if (str[i] == 'c') {
            if (i < str.length() - 1 &&  str[i + 1] == '=' || str[i + 1] == '-') 
                i += 2;
            else 
                i++;
            
            cnt++;
        }
        else if (str[i] == 'd') {
            if (i < str.length() - 2 && str[i + 1] == 'z' && str[i + 2] == '=') {
                i += 3;
            }
            else if (i < str.length() - 1 && str[i + 1] == '-') {
                i += 2;
            }
            else {
                i++;
            }
            cnt++;
        }
        else if (str[i] == 'l') {
            
            if (i < str.length() - 1 && str[i + 1] == 'j')
                i += 2;
            else
                i++;
            cnt++;
        }
        else if (str[i] == 'n' ) {
            if (i < str.length() - 1 && str[i + 1] == 'j')
                i += 2;
            else
                i++;
            cnt++;
        }
        else if (str[i] == 's' ) {
            if (i < str.length() - 1 && str[i + 1] == '=')
                i += 2;
            else
                i++;
            cnt++;
        }
        else if (str[i] == 'z' && str[i + 1] == '=') {
            if (str[i + 1] == '=')
                i += 2;
            else
                i++;
            cnt++;
        }
        else {
            cnt++;
            i++;
        }
    }
    cout << cnt;
    return 0;
}
 
 
cs


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

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

백준 1746번: 듣보잡 (C++)  (0) 2019.09.26
백준 1032번: 명령 프롬프트 (C++)  (0) 2019.09.26
백준 1316번: 그룹 단어 체커 (C++)  (0) 2019.09.25
백준 1157번: 단어 공부 (C++)  (0) 2019.09.25
백준 10809번: 알파벳 찾기 (C++)  (0) 2019.09.25

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


알파벳 26개 배열을 만들어서 해결



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
#pragma warning(disable :4996)
#include<iostream>
#include<string>
using namespace std;
 
int alp[26];
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    string str;
    
    int n, ret = 0;
    cin >> n;
    while (n--) {
        cin >> str;
        bool isBreak = false;
        for (int i = 0; i < str.length(); i++) {
            if (alp[str[i] - 'a'] > 0 && str[i] != str[i-1]) {
                isBreak = true;
                break; //이전 문자와 다른데, 이전에 나온적이 있는 단어인 경우
            }
            alp[str[i] - 'a']++;
        }
        if (!isBreak) 
            ret++;
 
        for (int i = 0; i < 26; i++)
            alp[i] = 0;
    }
    cout << ret;
    return 0;
}
 
cs


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

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

백준 1032번: 명령 프롬프트 (C++)  (0) 2019.09.26
백준 2941번: 크로아티아 알파벳 (C++)  (0) 2019.09.26
백준 1157번: 단어 공부 (C++)  (0) 2019.09.25
백준 10809번: 알파벳 찾기 (C++)  (0) 2019.09.25
백준 1707번: 이분 그래프 (C++)  (0) 2019.09.25

+ Recent posts

티스토리툴바