즐거운 사진 수집
문제 링크 : https://oj.uz/problem/view/JOI13_collecting 순서대로 10점 -> 30점 -> 100점 풀이를 최적화하는 과정을 통해 떠올렸다. 점수 배치도, 접근 과정도 굉장히 재미있는 문제였다. 일단 가장 단순하게 떠올릴 수 있는 해법부터 고려해보자. 사진의 어떤 일부분에 대해서, 그 사진을 4등분해야하는지 아닌지 조건을 우선 파악해야한다. 이건 비교적 간단한데, 해당 사진의 크기가 n*n이라고 했을 때, 위아래 선분이 0개 또는 n개 이면서 좌우 선분이 0개 또는 n개이면 해당 사진은 자르지 않아도 된다. 모든 선분이 다 0개 -> 전체 흰색, 둘 중 하나가 n개 -> 전체 검은색, 둘 다 n개 -> 전체 흰색이기 때문이다. 그러면 이제 여기서 4등분을 해야하는 경우..
Ojuz
2018. 3. 10. 23:11