PS 이야기

한글 문제임에도 불구하고 문제를 이해하기가 다소 까다로운 편이다. 이 문제는 DP로 해결할 수 있다. 가능한 상황은 $2^N \times 2^M$ 가지가 있다. 이는 최대 $2^{40}$ 가지로 경우의 수가 꽤 많다. 가능한 경우를 줄이도록 생각해야한다. 현재 상황에서 문제별로 채점이 되었는지, 아직 채점이 되지 않았는지 경우는 총 $2^M$가지가 있다. 그 중 한 상황에서 여태까지 살아남은 사람은 필요충분으로 여태까지 채점된 문제들에 대해서 모두 Yes라고 대답한 사람이다. 따라서, 어떤 문제들을 채점했는지를 알면, 살아남은 사람 또한 알 수 있게 된다. 따라서, DP를 $2^M$ 가지 경우에 대해서 돌리면 된다. #include #include using namespace std; const int ..