알고리즘 풀이

문제 보기사다리타기는 마치 시뮬레이션처럼 생각하여 2차원 배열로 구현할 수 있을 것으로 봤고, 가능한 경우를 구할 때에는 이미 있는 라인에서 최대한 지워보는 방식으로 구현하면 될 것으로 봤다. 결국 사다리타기 결과가 동일하기 위해선 반드시 기존 경우의 수의 부분집합으로

자바, 파이썬 풀이 포함

참고한 답을 이해하고 해석한 글입니다.

시뮬레이션 유형이므로 하라는대로 했을 때 시간이 초과할지 먼저 체크했습니다.

N이 최대 20만이므로 두 개씩 잡아가며 거리를 측정해서 수행하는 브루트포스로는 O(N^2)이므로 시간초과일게 뻔하다. 따라서 다른 방안을 선택해야 한다. 가장 간단한 방법은 거리를 미리 정해두고, 그 거리를 만족하는지 검증하는 로직으로 처리하는 것이다. 이는 파라메트

일단 1차원 배열을 직접 만들려면 O(N^2)라서 불가능합니다. 그렇다면 O(NlogN)의 풀이가 있을까 고민하게 되는데, 파라메트릭 서치를 이용하여 k번째 수가 될 수 있는 숫자를 임의로 대입해보면서 K번째 숫자가 될 수 있는지 로직을 구성하면 되겠다 생각했습니다.

Intuition 브루트포스 전략부터 생각해보면, 10001000을 탐색하면서 해당 좌표를 기준으로 다시 최악의 경우 10001000을 탐색하면서 정사각형의 크기를 가늠해야 하므로 이 로직으로는 풀어낼 수 없다. x,y 좌표 순회 자체를 막을 순 없으므로 각 좌표에서