코딩테스트/백준

[골4] 1043 - 거짓말

#include #include #include #include using namespace std; #define MAX 50 vector v(MAX); vector know; int parents[MAX]; int n, m, k; int Find(int x) { return x = (parents[x] == x) ? x : Find(parents[x]); } void Union(int x, int y) { parents[Find(x)] = Find(y); } int main() { ios::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(NULL); cin >> n >> m >> k; // 배열 초기화 while (k--) { int t; cin >> t; k..

[골5] 1916 - 최소 비용 구하기

#include #include #include #include #define INF 1e9 + 10 #define MAX 1001 #define y first #define x second using namespace std; using IntPair = pair; vector g[MAX]; priority_queue pq; vector dist(MAX, INF); int src, dst; void Dijkstra() { pq.push({ 0,src }); dist[src] = 0; while(!pq.empty()) { int cost = -pq.top().y; int cur = pq.top().x; pq.pop(); if (dist[cur] < cost) continue; for (int i = 0;..

[골4] 1753 - 최단 경로

#include #include #include #include #define INF 1e9 + 10 #define pi pair int v, e, st; using namespace std; vector adj[20005]; int d[20005] = { 0, }; void Dijkstra() { fill(d, d + 20005, INF); priority_queue pq; d[st] = 0; pq.push({ d[st],st }); while (!pq.empty()) { auto cur = pq.top(); pq.pop(); int dist = cur.first, idx = cur.second; if (d[idx] != dist) continue; for (auto& [cost, nidx] : adj..

[골4] 14502 - 연구소

참고해서 코드 작성 #include #include #include #include #define y first #define x second using namespace std; using IntPair = pair; using TwoDVec = vector; IntPair dir[] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; TwoDVec m, vm; vector vis; int h, w, ans = 0; // 바이러스 지도 초기화 함수 void SetMap() { for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) vm[i][j] = m[i][j]; } } void SpreadVirus() { queue q;..

[실1] 1074 - Z

#include #include #include #include #include #include #include #pragma warning(disable : 4996) using namespace std; int n, r, c, ans = 0; void dc(int x, int y, int size) { if (c == x && r == y) { cout = x && r >= y) { auto half = size / 2; dc(x, y, half); dc(x + half, y, half); dc(x, y + half, half); dc(x + half, y + half, half); } else ans += pow(size, 2); } int main() { ios::sync_with_stdio(0)..

[실1] 1697 - 숨바꼭질

for 범위 기반 임시 초기화 리스트를 이용해서 푼게 핵심이다. #include #include #include #include #include using namespace std; int dist[100002]; int n, k; int main() { ios::sync_with_stdio(0); cin.tie(0); fill(dist, dist + 100001, -1); cin >> n >> k; dist[n] = 0; queue q; q.push(n); while (dist[k] == -1) { int cur = q.front(); q.pop(); for (int nxt : {cur - 1, cur + 1, cur * 2}) { if (nxt 100000) continue; ..

[골5] 2170 - 선 긋기

#include #include #include #include using namespace std; #define y first #define x second bool cmp(pair& lRef, pair& rRef) { return lRef.y > n; vector v(n); for (int i = 0; i > v[i].y >> v[i].x; sort(v.begin(), v.end(), cmp); int s = INT_MIN, e = INT_MIN, ans = 0; for (int i = 0; ..

[실1] 9465 - 스티커

#include #include #include #include #include using namespace std; int main() { int c; cin >> c; while(c--) { int n; cin >> n; n++; vector dp(n, vector(n + 1)); for (int i = 1; i > dp[0][i]; for (int i = 1; i > dp[1][i]; for (int i = 2; i < n; i++) { dp[0][i] += max(dp[1][i - 1], dp[1][i - 2]); dp[1][i] += max(dp[0][i - 1], dp[0][i - 2]); } cout

[골4] 9252 - LCS 2

#include #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); string str1, str2; cin >> str1 >> str2; str1 = ' ' + str1; str2 = ' ' + str2; int n = str1.size(), m = str2.size(); vector v(n, vector(m)); stack s; for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (str1[i] == str2[j]) v[i][j] = v[i - 1][j - 1] + 1; ..

[골5] 9251 - LCS

#include #include #include using namespace std; int main() { string str1, str2; cin >> str1 >> str2; str1 = ' ' + str1; str2 = ' ' + str2; int n = str1.size(), m = str2.size(); vector v(n, vector(m)); for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (str1[i] == str2[j]) v[i][j] = v[i - 1][j - 1] + 1; else v[i][j] = max(v[i - 1][j], v[i][j - 1]); } } cout