반응형
1047번
-
1047번 : 울타리알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 9. 11:20
boj.kr/1047 1047번: 울타리 첫째 줄에 N이 주어진다. N은 2보다 크거나 같고, 40보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 나무가 심어져 있는 위치와 그 나무로 만들 수 있는 울타리의 길이가 순서대로 주어 www.acmicpc.net 아이디어 : 기준을 나무가 아닌, 울타리, 즉 직사각형에 초점을 맞추자. 직사각형은 가로선 2개와 세로선 2개로 만들 수 있고, 가로선 2개의 안쪽 영역과 세로선 2개의 안쪽 영역의 겹치는 부분이 곧 직사각형의 내부 영역이 된다. 가로 기준으로 나무(=점) 2개, 세로 기준으로 점 2개를 골라서 이 4개의 점이 이루는 직사각형을 먼저 구한다. 그 다음 직사각형에 포함되는 점들과 포함되지 않는 점들로 나눈다. 포함되지 않는 점들은 다 잘라놓고..