목록C++ (140)
정화 코딩
[C++] 쉬운 최단거리 (백준 14940번)
https://www.acmicpc.net/problem/14940 #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int diri[] = {1, -1, 0, 0}; int dirj[] = {0, 0, 1, -1}; int n, m; cin >> n >> m; vector> g = vector>(n, vector(m)); vector> d = vector>(n, vector(m, 0)); int sa, sb; for (int i = 0; i > g[i][j]; if (g[i][j] == 2) { ..
EDOC 2024-1 8회차 과제 (기하 알아보기)
A. 네 번째 점 (백준 3009번) https://www.acmicpc.net/problem/3009 //C++#include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); vector x = vector(3); vector y = vector(3); for (int i = 0; i > x[i] >> y[i]; } sort(x.begin(), x.end()); sort(y.begin(), y.end()); int ansx, ansy; if (x[1] == x[0]) ansx = x[2]; else ..
[C++] 반짝반짝 2 (백준 22984번)
https://www.acmicpc.net/problem/22984 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; double ans = 0; vector p = vector(n); for (int i = 0; i > p[i]; ans += p[i]; } for (int i = 0; i 각 전구 별로 켜질 확률을 전부 따로 계산한 후 전부 더해서 답을 구했다. 자연스럽게 확률과 통계에서 쓰던 사고 방식이 기댓값의 선형성이라는 알고리즘이었다. 풀이 자체는 어렵지 않았는데..
[C++] 호 안에 수류탄이야!! (백준 15889번)
https://www.acmicpc.net/problem/15889 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector loc = vector(n); vector avl = vector(n - 1); for (int i = 0; i > loc[i]; } for (int i = 0; i > avl[i]; } if (n == 1) { cout 0; i--) { if (loc[i] + avl[i] >= nxt) { ..
[AtCoder] ABC 355 (2024-05-25)
AtCoder Beginner Contest 355 (https://atcoder.jp/contests/abc355) A . Who Ate the Cake? https://atcoder.jp/contests/abc355/tasks/abc355_a //C++#include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); vector p = vector(4, true); for (int i = 0; i > x; p[x] = false; } int cnt = 0; int ans; for (int i = 1; i (정답) B..
[C++] 좌표 압축 (백준 18870번)
#include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector> data (n); vector ans = vector(n); for (int i = 0; i > data[i].first; data[i].second = i; } sort(data.begin(), data.end()); int cnt = 0; int tmp = 0; ans[data[0].second] = 0; int pre = data[0].first; for (in..
EDOC 2024-1 7회차 정모 (동적 계획법 알아보기 4)
A. 악수 (백준 8394번) https://www.acmicpc.net/problem/8394 //C++#include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector dp = vector(n + 1); dp[0] = 0; dp[1] = 1; if (n >= 2) { dp[2] = 2; } for (int i = 3; i (정답) B. 가장 큰 감소하는 부분 수열 (백준 17216번) https://www.acmicpc.net/problem/17216 //C..
EDOC 2024-1 7회차 정모 준비 (이분 탐색, 다이나믹)
공유기 설치 (백준 2110번) https://www.acmicpc.net/problem/2110문제 해석문제에서 주어진 예제를 그려보면 이렇게 된다. 1, 2, 4, 8, 9 위치에 집이 배치되어 있다. 이런 상황에서 가장 인접한 두 공유기 사이의 최대 거리는 공유기를 1, 4, 8에 설치하는 경우와 1, 4, 9에 설치하는 경우 모두 3이 된다. 이런 답은 어떤 과정으로 나오는 것일까? 우선 이 문제를 코드로 해결하는 게 아닌 인간인 우리가 푼다고 생각해보자. '대충 간격을 4 이상으로 둬볼까? 아 4이상으로 하니까 공유기가 남네... 그러면 좀 더촘촘히 둬도 될 것 같으니까 간격을 더 늘려서.....' 이런식으로 푸는 것이 자연스러워 보인다. 이런 경우에 사용되는 알고리즘이 이분 탐색이다.풀이//C..