Algorithm/Acmicpc
14658 하늘에서 별똥별이 빗발친다 [JAVA]
문제 풀이https://www.acmicpc.net/problem/14658n*m 구역에 k개의 별똥별이 주어지고 l*l 크기의 정사각형 트램펄린으로 이를 최대한 많이 튕겨냈을 때부딪히게 되는 별똥별의 수를 구하는 문제다 n*m 좌표에 대해 접근하거나 l의 길이에 대해 탐색을 하게 된다면 각 50만, 10만으로 수가 꽤 크기에 시간초과 혹은 메모리 초과가 발생할 가능성이 높다. 하지만, k가 100으로 매우 작기에 k^3의 풀이도 10^6으로 통과될 수 있다. 트램펄린에 별똥별이 최대로 담기고 최적으로 담기는 경우에 대해 생각해보면O O O O OO * * O OO * O O OO O * O O이런식으로 최대 4개를 가둘 수 있다고 생각할 수 있지만 이게 최적의 트램펄린 배치는 아니다.(왼변, 윗..
