N제한이 중요한데 n이 작으면 부르트포스로 풀면될거같음

이거 N-Queen문제인가 그거랑 비슷할 거 같은데

공을 고르는 순서는 중요하지 않은거같으니깐
비트마스크(또는 string key) + 메모이제이션쓰면 될듯

1뽑고 1을 뽑은뒤 가능한 것들에 대해 다 뽑음.
2도 뽑을 수 있으면 2뽑은 뒤 가능한 것들에 대해 다 뽑음.
뽑을 수 없는데까지 간 뒤 다시 버퍼를 비우고 2부터 다시 뽑음
이미 구해져있다면 구해진 값을 사용

간단한 예시로 공 8개중에 1,2,5,6을 뽑았고 더이상 뽑을게 없다면
m[11001100] = possible
이렇게 나타낼 수 있음

자료구조는 해시맵 같은거 쓰면 될거같고


1에선 2가 안되고 2에선 1이 되고 이런규칙이 생기면 다른 방법을 써야 할 듯

공이 아닌 점이라 생각하고
규칙이 점과 점에 선분이 놓아져잇다하면
최대한 많은 점을 잇는 문제임
한붓그리기 또는 다리건너기로 찾아보면 될듯

문제는 1번점은 3번점으로 이어지는데
3번점은 1번으로 안이어진다던가 이런 일방통행규칙이 어려운 부분이 될것같음

아니면 한점에서 다른점으로 가는 출발의 가짓수가 아닌
각 지점마다 다른 점에서 오는 가짓수를 배열하면 왠지 간단하게 답이 나올것같은 직감이 든다

고를 수 없는 공의 기준이 머징..?

1,2 를 동시에 고를 수 있으면, 1-2간선 연결하는 식으로 그래프를 그리면,

정답 = 부분 그래프 중에서, 가장 큰 완전 그래프의 크기

이렇게 되는데,

부분 그래프 중에서 완전 그래프 = Clique 라고 부르고, 여기에 대한 이것저것들이 있음.

가장 큰 clique를 찾는 게 가장 큰 이슌데, 위키 주소 남김.

https://en.wikipedia.org/wiki/Clique_problem

근데 플로우, MCMF로 할려고 했는데 증명이 계속 삑나서 보니까 별다른 조건 없이, 최대 clique를 찾는 건 NP라는 것 같음.

----

반대로 1,2를 동시에 고를 수 '없을 때', 1-2를 연결하는 식으로 생각할 수 도 있는데(결국 똑같은 얘기니까 이것도 NP겠지만)

조건을 좀 더 넣어서 다항시간으로 가능하게 만든 버전은 ACM 한국 대회에 나온 적 있음.

조건은 1->3, 3->4 이 있을 경우, 1->4도 있는 것.

http://weeklyps.com/entry/BOJ-8898-%EC%8A%A4%ED%8F%AC%EC%B8%A0-%EC%A0%84%EB%AC%B8-%EC%B1%84%EB%84%90-GSK