kth990303의 코딩 블로그

스터디그룹 채점현황 둘러보다가 발견한 문제. 결론부터 까고 말하자면, 이 문제는 BFS/DFS 뿐만 아니라 SCC로도 풀 수 있고, 만약 이게 정해라면 Platinum IV 티어 정도 받았을 것 같다. 문제 풀기 전에는 티어 열람 기능을 꺼놓기 때문에, 처음 봤을 땐 되게 쉬울줄 알았던 문제인데, 막상 풀 땐 그렇지 않았던 문제이다. 시간제한이 5초나 돼서 단순한 방법으로 풀리지만, 꽤 배울 점이 많은 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/1325 sync_with_stdio(0); cin>>n>>m; while(m--){ int a,b; cin>>a>>b; v[b].push_back(a); } int M=0; for(int j=1;j>a>>b; v[b]...

스터디그룹에서 연습 C번으로 진행된 문제. 어떻게 보면 되게 쉽지만, 어떻게 보면 마냥 쉽지만은 않은 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최 www.acmicpc.net 의식의 흐름 및 해설 물통 물 양이 각각 C, D가 되기 위한 최소 횟수를 구하는 문제. 이런 유형은 보통 BFS로 접근하는데, 문제는 N이 최대 10만이라 이차원배열로 방문체크를 하면 무조건 시간초과 혹은 메모리초과가 난..

생긴 건 되게 bfs 처럼 생겼는데 알고보니 bfs + bipartite matching + binary_search (필수는 아니지만) 가 복합적으로 사용되는 문제였다. https://www.acmicpc.net/problem/1348 1348번: 주차장 세준 주차장은 R*C크기의 직사각형 모양이다. 세준 주차장에는 N개의 차와, M개의 주차 구역이 있다. 그리고, 모든 차는 주차 구역에 주차하려고 한다. 교통 제한 때문에, 차는 주차장의 경계와 평 www.acmicpc.net 의식의 흐름 및 해설 하나의 주차장에는 하나의 차만 들어갈 수 있고, 그 외에 이동하면서 차끼리 충돌은 고려하지 않는다. (휴... 정말 다행이다. bfs로 충분히 할 수 있겠다.) 주차장과 차끼리 연결되는 모습이 이분그래프를 ..