코딩테스트/백준

[골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

[실1] 15724 - 주지수

#include #include using namespace std; #define SIZE 1050 int n, m, t, arr[SIZE][SIZE]{ 0 }; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 1; i a; arr[i][j] = a + arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1]; } } cin >> t; while (t--) { int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2; cout

[실4] 1120 - 문자열

#include #include #include using namespace std; int main() { string a, b; cin >> a >> b; int aLength = a.size(), bLength = b.size(); int res = INT_MAX; for (int i = 0; i