-
[BOJ] 16000 : 섬
16000 : 섬 풀이 문제를 조금 정리해 보자. 모든 섬 v에 대해, 최외곽 바다로 나가기 위해 반드시 거쳐야 하는 어떤 섬 u가 존재하는가? 섬들간의 어떤 관계에 대해서 묻고 있다. 관계는 항상 그래프로 나타낼 수 있다. 문제의 정의가 그래프스럽게 생겼으니, Flood-fill을 이용해 육지와 바다를 각각 노드로 묶어 그래프로 만들고 생각해보자. 그래프에서 최외곽 바다를 1번 노드로 두고 문제를 다시 생각해 보자. 모든 섬 노드 v에 대해, 1에서 v로 가기 위해 반드시 거쳐야 하는 섬 노드 u가 존재하는가?...
-
[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...
-
[BOJ] 15998 : 카카오머니
15998 : 카카오머니 풀이 주어지는 입력을 a[i], b[i]라고 하자. b[i]-b[i-1] == a[i]인 경우는 돈을 뽑아서 쓰지 않는 정상적인(?) 경우이다. b[i]-b[i-1] != a[i]인 경우는 비정상적인(?) 경우이다. 여기서 비정상적인(?) 경우도 두 경우로 나뉜다. 하나는 인출하지 않는 상황에서 남은 금액이 맞지 않는 경우, 이건 그냥 짜주자. 인출하는 경우에, 은행에서 인출하는 금액 k는 b[i]-b[i-1]-a[i]이다. 오 그렇다면 이러한 k가 여러개 있을 수 있는데, 우리가 구하는 건 공통된 k이므로 이러한 k들의 gcd를 구해주자. 그러한 gcd 값을 gcd_k라고 하자. 그럼 답이 모순되는...