PS/문제 풀이 (1) 썸네일형 리스트형 [ICPC 2020 Korea regional 풀이] 대회는 끝났지만 다시 풀어보면서 풀이를 올려보려고 한다. K. Tiling Polyomino 어제 문제가 올라왔지만 [계ㅡ측] 당해서 오늘 부관참시를 했다. 풀이는 굉장히 다양하게 존재하는 것 같으나 내 풀이(4500B)와 아인타 선생님의 훌륭한 풀이(1800B)를 적겠다. [4500B 망한 풀이] 모든 점의 deg가 2이므로 대부분의 경우 그래프가 뭉쳐있게 생겼다. 만약 deg가 2인 P의 점들이 모두 [관찰 1]이런 모양이라면, 단방향의 타일만 가지고도 덮을 수 있음이 쉽게 보장된다. [관찰 2]따라서 정사각형이 line을 이루게 될 경우만 따로 고려해주면 되고, 우리는 큰 컴포넌드들을 하나로 묶고, (deg가 2인) line의 점들로 이루어진 트리를 만들 수 있다. 트리의 리프는 무조건 큰 컴포넌트.. 이전 1 다음
