jaehon2002   10달 전

페이스북 해커컵 문제 푸신 분 있나요?

문제는 뭐 이해하는데 어려움이 없었지만 페이지에 공개된 해설을 봐도 이해 안되는 부분이 있는데

도전해서 다 푸신 분 안계신가요?

namnamseo   10달 전

A, B, C를 풀었는데 혹시 도와드릴 부분 있을까요..?

jaehon2002   10달 전

일단 A,B 문제만 보고 뒤는 걍 포기 했는데... ㅠ

A,B 문제는 완전히 이해 했습니다.

그런데 어떻게 풀어야 할지 뭔가 감이 잡힐듯 안 잡히네요.. ㅠ

뭔가 힌트라도...

namnamseo   10달 전

A는..
세 점 x,y,z에 대해서 x~y, y~z의 거리가 같은 점들을 찾는 거잖아요?
그렇다면 y를 고정해봅시다.
y로부터 같은 거리만큼 떨어져있는 점들이 있어야 하겠죠?
y로부터 거리가 r인 점이 k개 있다고 합시다. 이것의 경우의 수는 k개에서 2개를 고르는 방법의 수이므로 k·(k-1)/2 개죠. 이것을 이용하면 될 것 같습니다.
더 힌트 드릴까요?

B는..
일단 가로로 연속한 빈 칸을 생각해봅시다.
상식적으로, 두 개 이상의 빈칸이 가로로 연속해서 붙어있다면, 반대편을 꽉 채워서 경비원을 놓는 것보다는 그 안에 경비원을 놓는게 좋겠죠?
・・・・・ << 이 공간을

GGGGG
・・・・・

이렇게 채우는건 엄청 비효율적이라는 말이죠. G・・・・ 혹은 ・・G・・ 처럼 채울 수 있으니까요.
그럼 우선은 가로로 연속한 빈 칸마다 하나씩 경비원을 놓고 생각해봅니다.

그런데, 크기 1짜리 빈칸이 있다면? (X・X)
이 경우, 되도록이면 반대편의 '연속한 빈 칸'에 있는 경비원을 데려다가 세워놓으면 좋을 것 같습니다. (G는 ・・…・・들중 아무 곳에나 놓아도 되니까요.)
대신, 크기 1짜리 빈칸 여러 개를 커버할 수는 없습니다. 무슨 말인고 하니..
・X・
・・・
이런 부분이 있다면, 밑줄의 G로 왼쪽 빈칸을 막을 수도 있고 오른쪽 빈칸을 막을 수도 있지만, 하나만 막아야 한다는거죠

결국 정리하면 이렇게 됩니다.
 - 답은 연속한 구간의 갯수로 놓는다.
 - 각각의 크기 1짜리 빈칸에 대해서, 반대편을 본다.
     - 반대편이 연속한 빈 칸이라면, 그 빈칸을 아무도 가져가지 않았다면(?) 내가 가져간다.(내 위치에 경비원을 세운다는 것!) 그리고 답에서 1을 뺀다.
     - 반대편이 막혀있다면, 어쩔 수 없지...
     - 반대편이 크기 1짜리 빈칸이라면, 답에서 바로 1을 빼면 반대편의 그 빈칸을 볼때도 빼게 되기 때문에 적당히 잘(?) 처리한다.

jaehon2002   10달 전

A는  그럼

예제 인풋에 있는 것을 예로 들면

A(0,0) ,B(100,0) C(0,100) D(100,100)

A 고정 했을때 거리가 100인 점이 2개이고 100루트2 인점이 1개인데 그걸 둘 K(K-1)/2 로 해서 합하고

또 각 점마다 똑같은 방식으로 하면 된다는 거네요?

제가 이해 한것이 맞나요? 맞다면 거리가 100인 점이 2개 혹은 100루트2인 점이 1개인거는 배열 하나 만들어서 인덱스에 넣는 방식으로 하면 되겠죠?

B는 글 자체는 이해가 가는데 코드로 어떻게 해야 할지 아직 정리가 안되네요.. 좀 더 생각해 봐야할듯.. ㅠ

namnamseo   10달 전

A번은 맞습니다. 저는 한 점을 기준으로, 다른 점들을 거리순으로 정렬시키는 방법을 썼어요.
A를 기준으로 2·1/2 + 1·0/2 = 1개이고, 다른 네 개의 점들도 마찬가지이므로 4죠.

B번은... 화이팅입니다.
일단 구간들로 쪼개는 부분을 짜고 나시면 크게 어렵지는 않을 것 같아요. 각 점이 어느 구간에 속하는지 잘 기록하면..

댓글을 작성하려면 로그인해야 합니다.