전체 글
-
-
boj, 백준) 12008. 262144카테고리 없음 2021. 9. 21. 18:08
https://www.acmicpc.net/problem/12008 12008번: 262144 베시는 스마트폰 게임을 좋아한다. 요즘은 한 게임을 재미있게 즐기고 있다. 이 게임에서는 1 이상 40 이하의 정수 N(2 ≤ N ≤ 262,144)개로 이루어진 수열이 주어진다. 연속된 두 수가 같으면 합쳐 www.acmicpc.net 이 문제는 생각해보면 구조가 토너먼트?랑 비슷하단것을 알 수 있습니다. 토너먼트 형태의 문제는 대표적으로 https://www.acmicpc.net/problem/11066 (파일 합치기) 가 있습니다. 이런문제는 dp[i][j]를 i에서 j로 얻을 수 있는 최대 이런식으로 정의하면 풀 수 있습니다. 이 문제에서도 처음에 dp[i][j]를 i에서 j를 모두 사용해 만들 수 있는..
-
boj, 백준) 11281. 2-sat-4카테고리 없음 2021. 9. 20. 08:58
이 문제는 https://www.acmicpc.net/problem/11280 이 문제와 많이 유사합니다. 2-sat의 해의 조건을 알았으면 해를 하나 출력해야되는 문제입니다. 2-sat의 필요조건이 scc와 연관되는건 이해가 됐었는데 실제 해가 있는지는 헷갈렸는데 이 문제로 말끔히 해결됐습니다! 저는 어려워서 풀이를 봤는데 아이디어가 좀 멋져서 한번 생각해보는게 좋을 것 같습니다! __________________________________________________ 스포 방지 _______________________________________________________ #include #define Max 200020 using namespace std; int n, m, my_scc[Max..
-
boj, 백준) 16367. TV Show Game카테고리 없음 2021. 9. 20. 08:21
결국 심사위원의 세 선택중 두개는 정답과 같아야 하므로 세선택을 a,b,c 라 하면 (a v b) ^ (b v c) ^ (c v a) 로 나타낼 수 있어서 2-sat 문제가 됩니다. 단계별로 풀기에서 2-sat 으로 되어있길래 쉽게 풀었는데 2-sat 인걸 몰랐으면 좀 어려웠을 수도 있을 것 같습니다 ㅠㅠ #include #define Max 10100 using namespace std; int n, m, my_scc[Max]; vector vt[Max], rvt[Max], scc[Max]; bool visited[Max]; stack st; int f(int x) { if (x > n) return x - n; return x + n; } void g(int x, int y) { rvt[x].push..
-
boj, 백준) 4013. ATM카테고리 없음 2021. 9. 19. 12:55
#include using namespace std; #define INF 2000001000 #define MAX_V 500010 vector vt; vector rvt; vector scc; vector my_scc; bool visited[MAX_V]; vector scc_size; stack st; vector cost; vector dp; vector in; vector out[MAX_V]; vector candi; void dfs(int x) { visited[x] = true; for (auto n : vt[x]) { if (visited[n]) continue; dfs(n); } st.push(x); } int r; void dfss(int x, int t) { visited[x] = tr..
-
-
백준 3878 점 분리 c++ (증명)카테고리 없음 2021. 8. 25. 23:43
코드는 다른 블로그에 많으니 왜 두 점 집합의 볼록포가 서로 겹치지 않으면 분리하는 직선이 있는지에 대해 증명을 하도록 하겠습니다. 일반적으로 두 볼록도형 A,B가 서로 겹치지 않을 때 ( 교집합이 없을 때) 어떤 직선이 있어 두 도형을 분리시킴을 보입시다. A에 속하는 점 P와 B에 속하는 점 Q중 PQ의 거리가 가장 짧은 P와 Q를 선택해줍시다. 그리고 P와 Q를 의 수직 이등분선 l을 생각해줍시다. 이제 l이 조건을 만족함을 보입시다. 먼저 P, Q는 각각 A와 B의 경계에 있습니다. 증명은 PQ 선분과 A와 B의 경계사이 교점을 잡아주면 최소성으로 증명할 수 있습니다. 이제 P를 지나며 l에 평행한 직선 lP 를 생각해줍시다. lP는 A와 경계에서만 만납니다. 정확히 말하면 P를 기준으로 A의 왼..