https://www.acmicpc.net/problem/2538 2538번: 모눈종이 자르기 첫째 줄에는 모눈종이의 가로 길이와 세로 길이를 나타내는 자연수가 빈칸을 사이에 두고 주어진다. 가로와 세로의 길이는 모두 200000 이하이다. 둘째 줄에는 오려내고자 하는 다각형의 꼭짓점 www.acmicpc.net 완전 구현문제였다. 처음에는 조각을 판정하고 각 조각의 칸을 dfs로 돌며 모눈종이의 경계선 또는 다각형의 둘레에 접하는 수만큼 카운트하여 둘레를 직접 계산하는 것을 구현했는데 입력 조건이 가로 세로 길이가 20만이어서 시간초과가 난다는 사실을 깨달았다. 그래서 입력받은 다각형의 꼭짓점 위치를 바탕으로 조각의 둘레를 계산하는 방법으로 바꿨다. 문제에서, 다각형의 꼭짓점을 입력받을 때 시계반대방향..
'백준 2538' 태그의 글 목록