-
[BOJ] 16000 : 섬
16000 : 섬 풀이 문제를 조금 정리해 보자. 모든 섬 v에 대해, 최외곽 바다로 나가기 위해 반드시 거쳐야 하는 어떤 섬 u가 존재하는가? 섬들간의 어떤 관계에 대해서 묻고 있다. 관계는 항상 그래프로 나타낼 수 있다. 문제의 정의가 그래프스럽게 생겼으니, Flood-fill을 이용해 육지와 바다를 각각 노드로 묶어 그래프로 만들고 생각해보자. 그래프에서 최외곽 바다를 1번 노드로 두고 문제를 다시 생각해 보자. 모든 섬 노드 v에 대해, 1에서 v로 가기 위해 반드시 거쳐야 하는 섬 노드 u가 존재하는가?...
-
[BOJ] 14502 : 연구소
14502 : 연구소 풀이 삼성스럽다. 구현 문제다. 완전탐색 잘 짜주면 된다. 코드 #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; int n, m, s, a[11][11], chk[11][11]; vector<pair<int, int> > virus; int dfs(int x, int y) { int ret = 1; chk[x][y] = 1; for (int i = 0; i < 4; i++) { int nx = x+dx[i], ny...
-
[BOJ] 2842 : 집배원 한상덕
2842 : 집배원 한상덕 풀이 parametric search로도 풀릴 것 같은데 나는 투포인터로 풀었다. 높이가 될 수 있는 후보는 1000000개이지만 주어지는 그리드의 크기가 50*50이 최대이므로 많아야 2500개 후보가 있을 수 있다. 주어진 높이들을 정렬한 다음, 투포인터로 구간을 잡아 dfs를 돌려주자. 코드 #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int dx[] = { 0,0,-1,1,-1,-1,1,1 }; const int dy[] = { -1,1,0,0,-1,1,-1,1 }; int n, sx, sy, k, b[55][55], chk[55][55]; char a[55][55]; vector<int>...
-
[BOJ] 15997 : 승부 예측
15997 : 승부 예측 풀이 6개 각각의 경기마다 W, D, L 3개의 상태가 있으므로 최종 스코어는 총 3^6개의 경우가 나올 수 있다. 개수가 많지 않으니 완전탐색을 해주자. 마지막에 동률인 경우를 예외처리 하는 게 몹시 화가 나지만 인내심을 가지고 풀어보자. 코드 #include <bits/stdc++.h> #define fst first #define snd second using namespace std; map<string, int> m; struct abc { int x, y; double w, d, l; } a[6]; int s[4]; double r[4]; pair<int, int> t[4]; void go(int...
-
[codeforces] 1070H : BerOS File Suggestion
1070H : BerOS File Suggestion 풀이 주어지는 string의 길이가 엄청 짧다. 모든 substring을 다 잘라서 자료구조에 넣어주자. 그럼 쉽게 구현할 수 있다. 코드 #include <iostream> #include <algorithm> #include <map> #include <set> #include <string> using namespace std; int n, q; string a[10001]; map<string, pair<int, int> > m; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int k = 0; k < n; k++) { string str; cin >> str; a[k] = str; set<string> s; for...
-
[codeforces] 1070F : Debate
1070F : Debate 풀이 11을 모두 사용해주자. 01과 10을 모두 짝 지어주고 남은 01 또는 10을 00과 섞어서 값이 가장 큰 놈들을 최대한 사용해주자. 코드 #include <cstdio> #include <algorithm> #include <vector> using namespace std; int n, cnt, tot, sum; vector<int> v[4]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { int x, y; scanf("%d %d", &x, &y); if (x == 11) cnt++, tot++, sum += y; if (x ==...
-
[BOJ] 1023 : 괄호 문자열
1023 : 괄호 문자열 풀이 sgc109님 풀이 보고 구현했어요 괄호 문자열의 개수를 구하는 점화식을 구하고 (1)에서 괄호 ㄴㄴ 문자열의 개수를 구하는 점화식을 구하고 (2)를 역추적 하면 풀 수 있어요 코드 #include <cstdio> #include <cstring> typedef long long ll; const ll inf = 0x3f3f3f3f3f3f3f3f; int n; ll k, dp[55][105][2]; ll go(int now, int sum, int isWrong) { if (now == n) { return isWrong || sum!=50; } ll &ret = dp[now][sum][isWrong]; if (ret != inf) {...
-
[BOJ] 2453 : 부서 배치
2453 : 부서 배치 풀이 어떤 두 사람의 친하고 친하지 않고를 나타내는 관계가 있다. 관계는 항상 그래프로 표현할 수 있다. 이 문제에서 주어진 관계들을 그래프로 표현하면, 이 관계들이 여러 개의 Connected Component로 나눠질 수 있다. 부서는 반드시 2개가 존재하니까, 컴포넌트마다 그룹1에 들어가는 사람 수와 그룹2에 들어가는 사람 수를 정할 수 있다. 이를 정하는 과정에서 모순이 발생하면 -1을 출력하고 종료해주면 된다. 여기까지 각 컴포넌트마다 두 그룹에 할당되는 인원 수를 정했다. 이제 한 그룹의 사람들을 부서1에 배치할지,...
-
[codeforces] 1073C : Vasya and Robot
1073C : Vasya and Robot 풀이 널 향한 내 사랑은 여기까진가 봐. 그 사람 곁에서 행복하길 바라. 코드 #include <cstdio> int n, ex, ey, x[200002], y[200002]; char s[200002]; int abs(int x) { return x < 0 ? -x : x; } void f(char c, int &x, int &y) { if (c == 'U') y++; if (c == 'D') y--; if (c == 'L') x--; if (c == 'R') x++; } int main() { scanf("%d %s...
-
[codeforces] 1073D : Berland Fair
1073D : Berland Fair 풀이 안녕 내 사랑, 돌아보지마. 너 떠나도 나 울지 않을게. 부족했던 내가 더 많이 미안해. 이렇게 사랑이 끝나간다. 코드 #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; int n, mn = 2e9, a[200002]; ll t, ans; int main() { scanf("%d %lld", &n, &t); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (mn > a[i]) mn = a[i]; } while (mn <= t) {...