배열 안에서 마름모 꼴 모형을 키워 나가서 마름모 범위 안에 포함되는 집의 수 * 값 - 마름모 넓이(문제에서 구하는 방법 알려줌) >=0 일때, 마름모가 집의 수를 최대로 포함할 때의 집 수를 구하시오
Solved
완전 탐색으로 칸 지나갈 떄마다 다 확인함, 칸 별로 전부 고려해야함, 역시 삼성 문제.
UnSolved
Tips
제한시간이 3초, N<=20 이며 Big-O는 O(N3)이 나오므로 8,000번의 횟수로 예상할 수 있다. 하지만 문제를 풀다보면 3중 for문에서 호출하는 함수에서 또 k값에 따라 또 for문을 돌려야 하는데 4중 for문으로 간주해서 O(N4)으로 하는 것은 아닌 것 같다. 그렇게 되면 시간초과가 나야 하는데 그렇지 않거덩. 실제 삼성 문제 해설에서도 O(N3)으로 간주하는 것으로 확인.
branch : sheep1500 commit : 3c165a56e2cd6893cc7f523a710780e17795754a
About The Problem
Solved
UnSolved
Tips