백준 10265

10265번: MT

 

1. X가 안 가면 나도 안 간다는 말은 내가 가면 X도 간다는 말을 의미. 또 X가 간다고 반드시 내가 갈 필요는 없음.

 

2. 문제 조건에 따라 컴포넌트를 구하면 그 컴포넌트 내에 반드시 사이클이 존재함. 이 사이클에 속하는 사람끼리는 반드시 같이 가야되며, 컴포넌트에 속하는 그 외의 사람들은 갈 수도 있고 안 갈 수도 있음. 따라서 각 컴포넌트 당 버스 탑승 가능 인원은 최소 사이클에 속하는 사람 수, 최대 컴포넌트에 속하는 사람 수임.

 

3. 각 컴포넌트 당 가능 인원을 모두 구했으면 문제의 답을 구해야 하는데, 0-1 냅색을 응용해야함. 처음엔 2차원 0-1 냅색으로 dp를 짜려고 했으나 각 컴포넌트 탑승 인원이 범위를 가져서 dp를 어떻게 정의해야할지 몰라서 헤맴. 그냥 최댓값으로 정의하고 박았지만 모두 실패. 곰곰이 생각해보니 결정 문제로 바꿔서 풀면은 정의도 명확해지고 풀릴 것 같았음. dp[x]는 탑승 인원 x가 가능한가?로 정의.

 

4. 컴포넌트 하나만 고려했을 때 가능한 인원 업데이트, 컴포넌트 두 개를 고려했을 때 가능한 인원 업데이트 ... 순으로 쭉 업데이트 하면 됨.

주의할 점은 0 ~ k순으로 업데이트 하면 해당 컴포넌트를 중복으로 사용해서 업데이트 하는 꼴이 되니 반드시 역순으로 업데이트 해야 함.

 

- Source code link

github.com/Bibidi/Algorithms/blob/master/boj/boj%2010265.cpp