SCC5 BOJ 7535 - A Bug's Life https://www.acmicpc.net/problem/7535 7535번: A Bug’s Life The output for every scenario is a line containing “Scenario #i:”, where i is the number of the scenario starting at 1, followed by one line saying either “No suspicious bugs found!” if the experiment is consistent with his assumption about the bugs’ sexua www.acmicpc.net 각 항이 xor로 묶여있는 2-Sat문제이다. p번 벌레가 q번 벌레와 소통했을 때 둘의 성별이 달라야 한다. 이를 p x.. 2019. 8. 19. BOJ 4013 - ATM https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차로 번호와 끝 교차로 번호를 나타내는 2개의 정수가 주어진다. 그 다음 N개의 줄에는 1번 교차로부터 차례대로 각 교차로의 ATM 기기가 보유한 현금의 액수를 나타내는 정수가 각 줄에 하나씩 주어진다. 그 다음 줄에는 두 개의 정수 S와 P가 주어 www.acmicpc.net 중요한 문제라고 생각함. 유니온파인드 말고 SN, sn[MAX] 쓰면 더 쉽다. scc를 나누는데 레스토랑이 있는지, 시작점인지 등등 정보.. 2019. 8. 19. BOJ 10265 - MT (sAdj, 위상정렬, knapsack) https://www.acmicpc.net/problem/10265 10265번: MT 문제 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 말들을 주고받았다. 재혁: 동우가 안 가면 나도 안 간다. 동우: 세종이가 안 가면 난 안 갈래. 버스에 태울 수 있는 인원수는 한정되어 있는데 모두들 다른 누군가가 가지 않으면 자신도 가지 않겠다 하니 남규는 신경이 뻗쳤다. 게다가 술을 너무 많이 샀기 때문에 최대한 www.acmicpc.net 간선을 다음과 같이 잡아준다. u : 난 v없으면 안가 // v->u scc끼리 묶은 그래프를 보면, 한 컴포넌트씩 살펴봤을 때 ind가 .. 2019. 8. 19. 2-SAT(Boolean Satisfiability) F = (a||b) && (c||d) && (e||f).... (||대신 xor등으로 변형가능함) 다음과 같이 F가 주어질 때, 1. F가 참이나 거짓이 되도록 할 수 있는지 여부 2. F가 참/거짓일 떄 a,b,c,d,e,f,..의 값은 무엇인지 를 묻는 문제들이 대표적이다. 배경지식: 0. p->q == notp or q . p가 false라면 p->q는 항상 참이다. 1. p || q == notp -> q && notq->p (두 항이 대우관계로 같은 말이다. 방향이 반대인 그래프를 하나 더 그려주기 위함인 것으로 이해함.) 2. p xor q == (notp -> q && notq->p) && (p->notq && q->notp) (묶인 것 끼리 대우관계이다. 위와 같은 이유라고 이해함.) 3... 2019. 8. 19. 이전 1 2 다음