문제 링크 1. 분할 정복 문제 입력의 최대 크기가 20,000이므로 완전 탐색으로 풀기에는 시간 초과가 날 것. 2. 자세한 풀이는 책 참고 (p.196) $n$개의 판자를 절반으로 나눠 두 개의 부분 문제를 만들자. 최대 직사각형은 다음 세 가지 중 하나에 속할 것 1. 왼쪽 부분 문제에 존재 2. 오른쪽 부분 문제에 존재 3. 왼쪽과 오른쪽 부분 문제에 걸쳐서 존재 1번과 2번은 어렵지 않으나 3번의 경우 왼쪽, 오른쪽 부분을 높이가 높은 쪽으로 한 칸씩 확장하면서 찾자. 3. import java.util.Scanner; public class FENCE { static int[] h; public static void main(String[] args) { Scanner sc = new Scan..
분할 정복
문제 링크 1. 분할 정복 문제 완전탐색으로 풀 수 있지만, 효율적으로 문제를 풀기 위한 방법을 고안하자. 2. 자세한 풀이는 책 참고 (p.193) 무식한 방법은 쿼드 트리 압축을 풀어 실제 그림을 만들고 이를 반전하고 다시 압축하는 것 그러나, N이 엄청 클 때 점 하나만 다른 색이라면 매우 비효율적 압축을 다 풀지 않고 뒤집는다면? 1, 2, 3, 4분면이 3, 4, 1, 2사분면으로 바뀌는 아이디어 문자열 입력 부분에서 에러가 나서 뭐가 문제인지 고민을 많이 했다. sc.nextInt()에서 정수를 입력받은 뒤 엔터를 입력하면 개행 문자가 다음 sc.nextLine()의 입력으로 들어가 버린다. 이를 해결하기 위해 정수를 입력받고 나서 sc.nextLine()을 한번 실행 해주자. 3. impor..
