구사과

https://www.acmicpc.net/problem/10454 Observation 1. 모든 정점을 포함하는 최소의 직사각형을 가정하자. 이를 세 정사각형으로 채울 때, 세 정사각형 중 하나는 그 직사각형의 모서리를 모서리로 가지고 있다.-> 그렇지 않게 정사각형을 열심히 그려보면 (...) 알 수 있다. 케이스를 많이 나누는 식으로 증명이 되지 않을까.. 싶다. Observation 2. 모든 정점을 포함하는 최소의 직사각형을 가정하자. 이를 두 정사각형으로 채울 때, 두 정사각형 중 하나는 그 직사각형의 모서리를 모서리로 가지고 있다.-> 역시 그렇지 않게 정사각형을 열심히 그려보면 (...) 알 수 있다. Observation 3. X가 3SQ-sufficient 일때 X+1은 3SQ-suf..

https://www.acmicpc.net/problem/96612^k 일때의 풀이를 보고 꽤 고민하다가 풀었다. 내가 머리가 안 좋은갑다... N >= 5 이상일 때는 상대가 어떠한 전략을 쓰더라도 modulo 5 값을 같게 만들 수 있다.N = 1, N = 3, N = 4일 때는 어떠한 전략이어도 상근이가 이긴다.N = 0, N = 2일때는 어떠한 전략이어도 창영이가 이긴다. 고로 입력을 받은 후 모듈러에 따라 저 결과를 출력해주면 된다.

https://www.acmicpc.net/problem/2543 Interval Graph에서의 Vertex Cover의 개수라는 말로 이 문제를 한줄요약할 수 있다. 하지만 말하는 그대로 dp를 짜기에는 상황이 너무 복잡하다. dp가 애초에 되는지 잘 모르겠다. 여기서 Vertex Cover의 정의를 잠깐 훑고 가자면 "그래프의 모든 간선에 대해, 최소 1개의 정점이 집합 S에 속하도록 하는 정점의 부분집합 S" 이다. 때문에 S의 여집합 I는 "그래프의 모든 간선에 대해, 최대 1개의 정점이 집합 I에 속한다" 라는 성질을 만족한다. 즉 I는 그래프의 독립 집합이다. 즉 Vertex Cover의 여집합은 Independent Set이라는 것을 알고 있으면 이 문제를 풀 수 있다. Interval G..