-
[BOJ] 2492: 보석
2492: 보석 풀이 이 풀이를 참고하자. 복붙 날먹 꺼-억 아 이 문제는 사각형이 격자를 벗어나면 안 되니까 주의하자. 코드 #include <bits/stdc++.h> using namespace std; int n, m, t, k; int dap, dap_x, dap_y; struct abc { int x, y; } a[111]; void go(int x, int y) { int cnt = 0; for (int i = 1; i <= t; i++) { if (x <= a[i].x && a[i].x <= x+k && y <= a[i].y && a[i].y...
-
[BOJ] 2496: 금강석
2496: 금강석 풀이 (x, y)의 좌표계를 변환하자. (x, y) => (x+y, x-y)로 좌표를 변환시키면 좌표계가 45도 기울어지고, 점 사이의 간격이 root(2)배만큼 늘어난다. 좌표계를 돌리고 나면 마름모가 정사각형이 되므로, 문제를 풀기 한결 수월해진다. T가 100밖에 안 된다는 점을 주목하자. 정답에 포함되는 어떤 금강석들의 집합이 있다고 하자. 이 금강석들을 포함하는 사각형은, 얘네들을 모두 포함하는 선에서 이리저리 잘 옮길 수 있을 것이다. 정답을 벗어나지 않는 선에서, 사각형을 최대한 오른쪽 아래로 땡겨보자. 항상 두 개의 금강석이 왼쪽과 위쪽 변에...
-
[BOJ] 2437 : 저울
2437 : 저울 풀이 일단 주어진 추들의 무게를 정렬해 보자. 1~w까지의 모든 무게를 만들 수 있다고 가정하자. 1~w를 만들 수 있다면 여기에 무게 k의 추를 추가해서 1~w+k까지의 모든 무게를 만들 수 있다. 하지만 만약 k > w+1이라면 w+을 만들 수 없게 된다. 이제 코드로 옮겨보자. 코드 #include <cstdio> #include <algorithm> int n, a[1001]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } std::sort(a, a+n); int mx...
-
[BOJ] 2618 : 경찰차
2618 : 경찰차 풀이 dp[i][j] = 경찰차1이 i번째 사건, 경찰차2가 j번째 사건의 위치에 있을 때 거리 합의 최소값 일반성을 잃지 않고, max(i, j)까지의 사건들을 모두 처리했다고 하자. 지금 처리할 사건을 k번째라고 하자. (k = max(i,j)+1) dst(i, j)는 i번째 사건과 j번째 사건 사이의 거리를 구하는 함수라고 하자. 경찰차1이 k번째 사건을 처리하려면, dp[k][j] = dp[k-1][j] + dst(k, k-1) 경찰차2가 k번째 사건을 처리하려면, dp[i][k] = dp[i][k-1] + dst(k, k-1) 점화식을 잘 정의했다면 여기까지 어렵지 않게 떠올릴 수 있다....
-
[BOJ] 2453 : 부서 배치
2453 : 부서 배치 풀이 어떤 두 사람의 친하고 친하지 않고를 나타내는 관계가 있다. 관계는 항상 그래프로 표현할 수 있다. 이 문제에서 주어진 관계들을 그래프로 표현하면, 이 관계들이 여러 개의 Connected Component로 나눠질 수 있다. 부서는 반드시 2개가 존재하니까, 컴포넌트마다 그룹1에 들어가는 사람 수와 그룹2에 들어가는 사람 수를 정할 수 있다. 이를 정하는 과정에서 모순이 발생하면 -1을 출력하고 종료해주면 된다. 여기까지 각 컴포넌트마다 두 그룹에 할당되는 인원 수를 정했다. 이제 한 그룹의 사람들을 부서1에 배치할지,...
-
[BOJ] 8983 : 사냥꾼
8983 : 사냥꾼 풀이 어떤 동물을 사냥할 수 있는지 판단해야한다. 그러기 위해선 어떤 동물에서 가장 가까운 어떤 사냥대를 찾아야 한다. 동물의 y좌표는 모든 사냥대에 대해 절대적인 반면, x좌표는 사냥대에 대해 상대적이다. 그러므로 동물의 x좌표와 사냥대의 x좌표만 비교해서 O(1) 또는 O(log n)의 시간에 가장 가까운 사냥대를 찾을 수 있다. O(1)은 적당히 반복문을 잘 굴리면 되고 O(log n)은 적당히 이분탐색 같은 걸 사용하면 된다. (안 해봤지만 아마 될 거다 ㅎ) 코드 #include <cstdio> #include <algorithm> using namespace...
-
[BOJ] 1713 : 후보 추천하기
1713 : 후보 추천하기 풀이 짜라는대로 짜면 된다. 코드 #include <cstdio> #include <deque> #include <algorithm> using namespace std; int n, m; struct abc { int idx, vote, time; bool operator <(abc a)const { if (vote == a.vote) return time < a.time; return vote < a.vote; } }; int main() { deque<abc> d; scanf("%d %d", &m, &n); for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); for (abc &it : d)...
-
[BOJ] 15969 : 행복
15969 : 행복 풀이 돌려돌려~ 돌림판~ 코드 #include <cstdio> int n, x, mn = 1e9, mx = -1e9; int main() { scanf("%d", &n); while (n--) { scanf("%d", &x); if (mn > x) mn = x; if (mx < x) mx = x; } printf("%d", mx - mn); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 11899 : 괄호 끼워넣기
11899 : 괄호 끼워넣기 풀이 왠지 그냥 짜면 돌아갈 것 같았어 코드 #include <cstdio> #include <stack> using namespace std; char s[55]; stack<char> stk; int main() { scanf("%s", s); for (int i = 0; s[i]; i++) { if (!stk.empty() && stk.top() == '(' && s[i] == ')') stk.pop(); else stk.push(s[i]); } printf("%d", stk.size()); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제...
-
[BOJ] 15973 : 두 박스
15973 : 두 박스 풀이 노가다를 해보자~ 사실 노가다 안 해도 됨 코드 #include <iostream> #include <string> using namespace std; int x[5], y[5]; string gogo() { if (x[0] == x[3] && y[0] == y[3] || x[1] == x[2] && y[0] == y[3] || x[0] == x[3] && y[1] == y[2] || x[1] == x[2] && y[1] == y[2]) return "POINT"; if (x[0] == x[3] && y[2] <= y[0] && y[0] <= y[3] || x[0] ==...
-
[BOJ] 1866 : 택배
1866 : 택배 풀이 , 코드 #include <cstdio> #include <algorithm> using namespace std; int n, t, h, a[3003], dp[3003]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); scanf("%d %d", &t, &h); sort(a + 1, a + 1 + n); for (int i = 1; i <= n; i++) { dp[i] = dp[i - 1] + a[i] * t; int cst = h; for (int j = i;...
-
[BOJ] 10804 : 카드 역배치
10804 : 카드 역배치 풀이 . 코드 #include <cstdio> #include <algorithm> using namespace std; int n = 10, a[21]; int main() { int l, r; for (int i=1;i<=20;i++) a[i] = i; while (n--) { scanf("%d %d", &l, &r); reverse(a + l, a + r + 1); } for (int i=1;i<=20;i++) { printf("%d ", a[i]); } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘,...
-
[BOJ] 1977 : 완전제곱수
1977 : 완전제곱수 풀이 음 잘 세어주면 된다 코드 #include <stdio.h> int min(int a, int b) { return a < b ? a : b; } int a, b, sm, mn = (int)1e9; int main() { scanf("%d %d", &a, &b); for (int i = 1; i*i <= b; i++) { if (i*i >= a && i*i <= b) { mn = min(mn, i*i); sm += i*i; } } if (!sm) printf("-1"); else printf("%d\n%d", sm, mn);...
-
[BOJ] 10159 : 저울
10159 : 저울 풀이 a와 b의 대소관계를 알 수 있다는 것은 a에서 b까지 알고 있는 관계를 건너건너 도착할 수 있다는 것이고 n 제한이 100으로 엄청 작으므로 모든 경로를 구해놓자. 그리고 도달할 수 없는 노드의 개수를 세어주자. 코드 #include <stdio.h> int n, m, a[101][101]; int main() { scanf("%d %d", &n, &m); for (int i = 0, x, y; i < m; i++) scanf("%d %d", &x, &y), a[x][y] = 1; for (int k = 1; k <=...
-
[BOJ] 10158 : 개미
10158 : 개미 풀이 개미가 움직이는 w*h 크기의 격자가 사방에 이어붙여져 있다고 생각해보자. w - abs(w - (x + t) % (2 * w)), h - abs(h - (y + t) % (2 * h)) 나머지 연산을 이용하면 간단하게 풀 수 있다. 코드 #include <bits/stdc++.h> int w, h, x, y, t; int main() { scanf("%d %d %d %d %d", &w, &h, &x, &y, &t); printf("%d %d", w - abs(w - (x + t) % (2...
-
[BOJ] 10157 : 자리배정
10157 : 자리배정 풀이 달팽이 짜듯이 하면 된다 코드 #include <stdio.h> const int dx[] = { 1,0,-1,0 }; const int dy[] = { 0,1,0,-1 }; int n, m, c, a[1002][1002]; int main() { scanf("%d %d %d", &n, &m, &c); for (int i = 0; i <= 1001; i++) a[i][0] = a[0][i] = a[m + 1][i] = a[i][n + 1] = 1; int x = 0, y = 1, d = 0; for (int i =...
-
[BOJ] 10156 : 과자
10156 : 과자 풀이 꺄르륵 코드 main(a,b,c){scanf("%d%d%d",&a,&b,&c);printf("%d",a*b-c>0?a*b-c:0);} 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 2459 : 철사 자르기
2459 : 철사 자르기 풀이 문제를 끝까지 안 읽어서 직선의 위치를 직접 정해야 하는 줄 알았는데 알고보니 직선의 위치를 문제에서 주는 거였다. i번째 점과 i+1번째 점의 좌표를 이용해서 어찌저찌 잘 짜면 된다. 코드 #include <bits/stdc++.h> #define fst first #define snd second using namespace std; int n, k, l; pair<int, int> p[100002]; int main() { scanf("%d %d", &n, &k); for (int i = 0; i < k; i++) scanf("%d %d", &p[i].fst, &p[i].snd); p[k++] = { 1,1...
-
[BOJ] 2458 : 키 순서
2458 : 키 순서 풀이 모든 노드에서 dfs를 정방향으로 한 번, 역방향으로 한 번 돌려주자! 정방향은 나보다 큰 친구들, 역방향은 나보다 큰 친구들의 개수(?)이다. 이 둘을 합한 값이 나를 제외한 n-1명과 같은지 알아보자! 코드 #include <bits/stdc++.h> using namespace std; int n, m, t, vst[2][501]; vector<int> gph[2][501]; int dfs(int now) { int ret = 1; vst[t][now] = 1; for (int nxt : gph[t][now]) if (!vst[t][nxt]) ret += dfs(nxt); return ret; } int main() { int u,...
-
[BOJ] 2457 : 공주님의 정원
2457 : 공주님의 정원 풀이 회의실 배정 문제에 날짜가 추가된 버전이다. 정렬해서 그리디를 돌리면 된다. 날짜를 처리하기가 조금 까다롭다. 하지만 까다로운 건 싫다. 그렇다면 month에 100을 곱해보자. 기적이 일어난다. 코드 #include <stdio.h> #include <algorithm> #define fst first #define snd second using namespace std; int n; pair<int, int> f[100001]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c,...
-
[BOJ] 2456 : 나는 학급회장이다
2456 : 나는 학급회장이다 풀이 완전 쌩노가다 문제! 점수 합이 같은 경우에는 높은 점수의 개수(?)를 비교해야 한다. 점수의 개수를 카운팅하지 말고, 점수를 제곱해서 더해주자! 점수의 개수에 따라 제곱합 값이 달라지기 때문에 점수의 개수가 다르다면 unique함이 보장된다. 잔재주를 조금 부리면 코드 길이를 엄청 줄일 수 있다. 코드 #include <stdio.h> #include <algorithm> #define fst first #define snd second using namespace std; int n, f; pair<int, int> p[3]; int main() { scanf("%d", &n); for (int i = 0;...
-
[BOJ] 2455 : 지능형 기차
2455 : 지능형 기차 풀이 기차 뿌뿌 코드 #include <stdio.h> int s, m; int main() { for (int i = 0; i < 4; i++) { int a, b; scanf("%d %d", &a, &b); s = s - a + b; m = m > s ? m : s; } printf("%d", m); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge
-
[BOJ] 2565 : 전깃줄
2565 : 전깃줄 풀이 LIS를 구해주자! 주어진 두 축을 주어진 선으로 연결했을 때 겹치는 선이 없어야 한다! 한 축 x를 기준으로 잡아 pair를 정렬해주자. 이제 정렬한 축 x를 기준으로 한바퀴 쭉 돌면서 순서대로 마주치는 y축에 대해서 LIS를 수행해주자! 코드 #include <stdio.h> #include <algorithm> #define fst first #define snd second using namespace std; int n, len, lis[100]; pair<int, int> a[100]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d %d",...
-
[BOJ] 2591 : 숫자카드
2591 : 숫자카드 풀이 n-1번째 숫자와 n번째 숫자로 만든 값이 10~34면 dp[n-2]를 플러스 n번째 숫자가 0보다 크면(단독으로 숫자를 구성할 수 있으면) dp[n-1]을 플러스 코드 #include <stdio.h> int i, a[44], dp[44]; int main() { dp[1] = 1; for (i = 2; ~scanf("%1d", &a[i]); i++) { if (a[i]) dp[i] += dp[i - 1]; if (a[i] + a[i - 1] * 10 > 9 && a[i] + a[i - 1] * 10 < 35) dp[i] += dp[i -...
-
[BOJ] 2583 : 영역 구하기
2583 : 영역 구하기 풀이 직사각형 영역에 체크를 해놓고 모든 칸을 돌면서 bfs나 dfs나 아무거나 돌려주면 된다. 입력이 좀 짜증난다 (…) 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int dx[] = { -1,0,1,0 }; const int dy[] = { 0,-1,0,1 }; int n, m, k, cnt, a[111][111]; vector<int> v; int dfs(int x, int y) { int ret = 1; a[x][y] = 1; for (int i = 0; i < 4; i++)...
-
[BOJ] 7576 : 토마토
7576 : 토마토 풀이 bfs를 돌리자 코드 #include <cstdio> #include <queue> #include <algorithm> using namespace std; const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; int n, m, a[1003][1003]; queue<pair<int, int> > que; int main() { scanf("%d %d", &m, &n); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &a[i][j]); if (a[i][j] == 1) que.push({ i,j }); }...
-
[BOJ] 13306 : 트리
13306 : 트리 풀이 엣지를 제거하면서 union find를 하려면 TLE가 난다. 문제를 거꾸로 생각하자. 원래의 문제는 간선이 모두 이어진 상태에서 하나씩 제거하는 형태이다. 그렇다면 역으로 간선을 다 끊어놓고 쿼리를 뒤에서 부터 돌면 되지 않을까?! 간선을 하나씩 이어주면서 union find를 돌리게 되면 빠르게 답을 구할 수 있다. 발상의 전환이 조금 어려운 문제인 것 같다. 코드 #include <bits/stdc++.h> using namespace std; const int n_ = 2e5 + 3; int n, q; int gph[n_], pnt[n_], q1[n_ * 2],...
-
[BOJ] 2623 : 음악프로그램
2623 : 음악프로그램 풀이 위상정렬을 하면 된다! 코드 #include <iostream> #include <vector> using namespace std; const int n_ = 1000 + 3; int n, m, idg[n_]; vector<int> ans; vector<int> edg[n_]; void dfs(int now) { idg[now] = -1; ans.push_back(now); for (auto nxt : edg[now]) if (!(--idg[nxt])) dfs(nxt); } int main() { int i, j, a, b, c; cin >> n >> m; while (m--) { cin >> a >> b; while (--a) { cin >> c;...
-
[BOJ] 2511 : 카드놀이
2511 : 카드놀이 풀이 구현을 하자. 코드 #include <bits/stdc++.h> using namespace std; int a[10], b[10], i, A, B, p; int main() { for (i = 0; i < 10; i++) scanf("%d", &a[i]); for (i = 0; i < 10; i++) scanf("%d", &b[i]); for (i = 0; i < 10; i++) { if (a[i] > b[i]) A += 3, p = 0; else if (a[i] < b[i]) B += 3, p = 1; else A++, B++;...
-
[BOJ] 10828 : 스택
10828 : 스택 풀이 스택을 쓰자. 코드 #include <bits/stdc++.h> using namespace std; int n, a; stack<int> sta; string str; int main() { for (scanf("%d", &n); n; n--) { cin >> str; if (str == "push") { scanf("%d", &a); sta.push(a); } else if (str == "pop") { if (sta.empty()) printf("-1\n"); else printf("%d\n", sta.top()), sta.pop(); } else if (str == "size") { printf("%d\n", sta.size()); } else if (str == "empty") { printf("%d\n", sta.empty()); } else { if...
-
[BOJ] 13308 : 주유소
13308 : 주유소 풀이 2016 koi 전국대회 2번 문제이다. 뭔가 코드가 dp인 것 같기도 하고 아닌 것 같기도 한데 어쨌든 다익스트라+dp 그런 느낌으로 풀었다. 음 생각해보니 dp가 맞네 dp[i][j] = 노드i에서 기름값j로 놓고 풀면 된다! 여기서 트릭(?)을 한 번 써보자. priority_queue에서 dst가 가장 작은 노드부터 꺼내기 때문에 dp[i][j] (== vst[i][j])에 방문했었다면 이미 지금보다 작은 값으로 방문했었음이 보장된다. 그래서 bfs 돌릴 때랑 똑같이 풀면 된다. visted면 방문하지 않아도 된다. 코드 #include <bits/stdc++.h> using namespace std; typedef...
-
[BOJ] 10799 : 쇠막대기
10799 : 쇠막대기 풀이 괄호가 나오는 문제는 대부분 stack을 이용하면 풀린다! 룰루랄라 코드 #include <bits/stdc++.h> using namespace std; int cnt, ans; string str; int cmp(char a, char b) { a -= '(', b -= '('; if (a == 0 && b == 0) return 1; if (a == 0 && b == 1) return 2; if (a == 1 && b == 0) return 3; if (a == 1 && b == 1) return 4;...
-
[BOJ] 10801 : 카드게임
10801 : 카드게임 풀이 단순 구현. 코드 #include <bits/stdc++.h> using namespace std; int a[20], x, y; int main() { for (int i = 0; i < 20; i++) scanf("%d", &a[i]); for (int i = 0; i < 10; i++) { if (a[i] > a[i + 10]) x++; if (a[i] < a[i + 10]) y++; } if (x > y) puts("A"); else if (x < y) puts("B"); else puts("D"); return 0; } 아무말 백준, 백준 온라인...
-
[BOJ] 2661 : 좋은 수열
2661 : 좋은 수열 풀이 재귀로 작은 숫자부터 들어가면서 문자를 비교해주자 코드 #include <bits/stdc++.h> using namespace std; int n, a[88]; void gogo(int cnt) { for (int i = 1; i <= cnt / 2; i++) { if (equal(a + cnt - i, a + cnt, a + cnt - i - i)) return; } if (cnt == n) { for (int i = 0; i < n; i++) printf("%d", a[i]); exit(0); } for (int i...
-
[BOJ] 13305 : 주유소
13305 : 주유소 풀이 지금 주유소보다 더 작은 주유소가 나올 때 까지 누적하며 풀면 된다. 그리디! 코드 #include <bits/stdc++.h> using namespace std; const int n_ = 1e5 + 10; int n, i, val, dst[n_], prv = 1e9 + 10; long long ans; int main() { scanf("%d", &n); for (i = 0; i < n - 1; i++) scanf("%d", &dst[i]); for (i = 0; i < n - 1; i++) { scanf("%d", &val); prv = min(prv,...
-
[BOJ] 2531 : 회전 초밥
2531 : 회전 초밥 풀이 범위를 나타내는 left와 right를 두고 inch worm으로 계산해나가면 된다. 근데 그냥 반복문으로도 풀 수 있다. 코드 #include <stdio.h> #include <algorithm> using namespace std; int N, D, K, C; int sushi[30000 + 3000 + 3]; int cur_cnt[3000 + 3], cur_ans; void push(int sushi_num) { if (!cur_cnt[sushi_num]) ++cur_ans; ++cur_cnt[sushi_num]; } void pop(int sushi_num) { --cur_cnt[sushi_num]; if (!cur_cnt[sushi_num]) --cur_ans; } int main() { scanf("%d %d %d %d", &N, &D, &K, &C); for (int...
-
[BOJ] 13302 : 리조트
13302 : 리조트 풀이 다이나믹 프로그래밍! dp[i][j] = i번째 날에 쿠폰 개수가 j인 경우의 수! 룰루랄라 코드 #include <bits/stdc++.h> using namespace std; const int n_ = 100 + 10; const int price[] = { 0,10000,25000,37000 }; const int INF = 987654321; int n, m; int dp[n_][n_ * 2]; bool chk[n_]; void upd(int i, int j, int v) { if (dp[i][j] > v || dp[i][j] == INF) dp[i][j] = v; } int main() { scanf("%d %d",...
-
[BOJ] 2532 : 먹이사슬
2532 : 먹이사슬 풀이 문제를 풀고 나서 다른 분들의 코드를 보다가 lower_bound를 저렇게 쓸 수 있다는 사실에 감명받았다. 양수가 음수로 변하면, 양수일 때 더 큰 수가 음수에선 더 작은 수가 되는데 양수 중에서 작은 수와 음수 중에서 가장 작은 수를 고르게 되면 넓은 범위를 찾게 된다. *lower_bound(res, res + i, now) = now;를 통해 먹이사슬인지 판단할 수 있다. 새로운 데이터가 쌓이지 못하고 덮어쓰게 되면 INF의 값이 배열의 뒤쪽에 누적되게 되고, INF의 lower_bound가 답이 된다. 코드...
-
[BOJ] 2611 : 자동차경주
2611 : 자동차경주 풀이 처음 문제를 보자마자 다익스트라 풀이를 떠올렸는데 문제를 다시 읽어보니 1번 노드를 거치지 않고 다시 원래 노드로 돌아 올 수 없다 이거 싸이클도 없고 완전 DAG잖아? 위상정렬해서 풀려고 했는데 생각해보니 dp로 풀 수 있잖아? 코드 #include <stdio.h> #include <vector> using namespace std; const int n_ = 1000 + 1; int n, m, dp[n_], route[n_]; vector<pair<int, int> > gph[n_]; int dfs(int now) { if (!dp[now] && now != 1) for (auto nxt :...