어제 데브매칭 1번 왜 틀린건지 이해가 안간다

[익명(223.62)]

내가 푼 풀이가 0을 수직선에서 처음 0으로 두고나서 1번부터 n-1번까지 백트래킹에서 점을 두는 과정에서 0번부터 현재 인덱스 이전의 점까지 제대로 거리가 맞는지 안맞는지 일일이 확인하는 재귀하는 방식으로 풀었거든?심지어 종이에까지 그려가면서 했는데 아무리 봐도 틀린곳이 없는데 도대체 이 방식이 왜 틀렸다는거지?반례가 존재함?심지어 long값으로 둬서 자료형 반례까지 모두 틀어막았는데 왜그런거지 하..

[익명(223.38)]

0을 기준으로 n-1까지 점들을 백트래킹으로 놓으면, 1을 놓을때 0을 기준으로 우측,좌측에 놓고 그게 dist의 값과 일치하는지를 판별 하는 알고리즘으로 짜야함. 0과 1을 놓았을 때,2를 놓는다면,0을 기준으로 우측/좌측에 놓고 0-2와 0-1의 거리를 검사해야함. 이런식으로 n-1까지 백트래킹 하는식으로 구현했으면 시간복잡도는 몰라도

[익명(223.38)]

정확도 문제는 없을듯. 그런데 풀이를 보면 우측,좌측을 고려 안한듯

[익명(110.11)]

우측 좌측도 고려했음

[익명(110.11)]

1점이 0점을 기준으로 우측 좌측일때 나누고 다시 2점일때 좌측 우측일때 나눠면서 각각 지금까지 뒀던 점까지 거리 비교하는식으로 짰음

[익명(110.11)]

대신 바로 직전 점을 기준으로 우측 좌측 나눴음

[익명(110.11)]

근데 바로 뒀던 점을 기준으로 나눠도 문제 없는게 어차피 점 하나하나 거리를 비교해서 문제없다고 생각한거임