PS
-
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, 백준) 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..
-