kth990303의 코딩 블로그

굉장히 유명한 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/11014 11014번: 컨닝 2 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 1014번 컨닝은 N, M 제한이 80이 아니라 10이라는 점 외엔 11014번과 동일하다. 의식의 흐름 및 해설 사실 이 문제는 너무나도 유명한 문제여서 최대유량, bitmask+dp 로 풀어야한다는 사실 자체는 알고 있었던 문제이다. 그러나 왜 최대유량으로 풀리는지 모르는 상태였기 때문였었고, 마침 우연히 최근에 flow 관련 그래프 이론을 공부중이기 때문에 ..

flow 이론에 있어서 나름 구현은 쉽지만 중요한 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/1867 1867번: 돌멩이 제거 첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째 숫자는 행 번호, 두 번째 숫자는 열 번호를 나타낸다. www.acmicpc.net 의식의 흐름 및 해설 특정 행, 열을 최소한으로 선택하여 모든 돌멩이를 제거하는 문제이다. 행을 선택하면 그 행에 포함된 돌멩이의 열들이 영향을 받는다. 단, 다른 행들은 영향을 받지 않는다. 따라서 행과 열로 이분그래프를 나눠볼 수 있다. 여기서 돌멩이는 행-열을 연결하는 간선을 의미한다..