songgj123   6년 전

이진 탐색으로 풀었습니다.

mid에 왼쪽 사람과 오른쪽 사람 모두 닿지 못하면 0을 반환합니다.

mid를 어느 쪽으로 옮겨도 한 명 이상은 닿지 않기 때문입니다.

오른쪽 사람만 닿지 못하면, mid를 오른쪽으로 옮기고

왼쪽 사람만 닿지 못하면, mid를 왼쪽으로 옮깁니다.


이 방법이 정답이라고 생각하고, 예제도 정답이 나오는데

자료형 때문인지, 반복문 조건 때문인지

오답이 나옵니다.

왜 그럴까요??

chogahui05   6년 전

BinarySearch로 풀면 (Parametric Search) 

시간 복잡도가 O(nlogn)쯤 되지만 코드는 간결해지긴 해요. 

전 그렇게 안 풀었지만요.


문제는..

T가 소숫점 넷째 짜리까지라는 건데요. 이 말은 거리 또한 소숫점 넷째 자리까지 나타나질 수 있다는 것이지요.

당연히 실수와 실수는 == 비교하면 곤란합니다. 어떻게 정수형으로 바꿔서 같은 부등식으로 만들지 먼저 생각해 보세요.

이게 새로 올라온 선린고 문제 중에서 2~3번째로 어려운 문제일 겁니다.


같은 이유로 모 대학의 이 문제도 AC수가 난이도에 비해 상당히 낮습니다.

songgj123   6년 전

고민해 봐야겠네요

근데 binary search 말고 어떤 알고리즘으로 푸셨나요??

chogahui05   6년 전

저는 노가다로 풀었습니다.

간단하게 말하자면 부등식의 교집합 구하는 건데요.

사실 acm icpc의 예선 문제인 교차점과 비슷한 식으로 접근하면 풀리긴 하더라고요.

simm4256   6년 전

각 사람마다 갈 수 있는 범위가 있습니다.

1번 예제의 경우

첫 번째 사람은 1에서 출발해 오른쪽으로만 간다면 1+2.5*2 만큼 갈 수 있고

왼쪽으로 간다면 1-2.5*2만큼 갈 수 있습니다.

즉, 첫 번쨰 사람이 시간 내에 도달할 수 있는 위치는 max(0,1-2.5*2) ~ min(1e9,1+2.5*2) => 0~6 입니다.

두 번째 사람으로 넘어갑니다.

두 번째 사람이 갈 수 있는 범위는 7-2.5*1 ~ 7+2.5*1 => 4.5~9.5 까지겠네요.

마지막으로 세 번쨰 사람은

2.5~7.5 가 갈 수 있는 범위입니다.

세 범위의 교집합이 존재하면 세 사람은 만날 수 있습니다.

이 예제의 경우 교집합은 4.5~6 이니 세 사람은 4.5부터 6까지의 거리에 해당하는 복도에서 만날 수 있습니다.

교집합이 존재하지 않는다면 누군가 한명쯤은 반드시 낙오된다는 뜻이므로 만날 수 없습니다.

이를 각 사람마다 반복하면 O(N)의 알고리즘이 나옵니다.

songgj123   6년 전

겹치는 범위로 다시 코딩했는데

소수 오차에서 오답이 나오네요...ㅜ

어떤 식으로 처리하셨는지 코드 좀 올려주실 수 있을까요??

chogahui05   6년 전

제가 윗 댓에서도 말했다 시피 소수 오차가 생각보다 많이 골때립니다.

이 문제 같은 경우는 꽤 정밀해야 해서.. 단순히 엡실론을 이용해서 쓰는 게.. 어려울 듯 싶고요.

링크 건 문제도 같은 이유로 난이도에 비해 ac수가 엄청나게 적습니다.


방법은 간단한데요.

어짜피 소수점 4자리 아닙니까? 파싱하면 됩니다. 어떻게 하면 좋을까요?

일단 strtok이던 java의 split이던. .을 기준으로 분리합니다.

만약에 토큰이 1개가 나온다면 정수부만 있는 것이죠.

2개가 나오면 소수부까지 있는 거죠.


정수부에는 10000을 곱합니다.

예를 들어 2가 입력되면 2.0000 * 10000 = 20000이 되죠?

소수부는 2번째 토큰으로 알 수 있는데요.


2.3 같은 경우에는 2와 3으로 토큰이 분리됩니다.

2.3000은 2.3과 같죠? 1번째 자리에만 1000을 곱합니다.

소수부에 1000을 곱하고. 정수부에 10000을 곱한 걸 더하면 23000이죠.


만약에 T가 2.565면 어떻게 하면 될까요?

2와 565로 쪼개집니다. 그렇기 때문에 565에 10을 곱한 5650이 소수부가 되는 것이죠.

어떻게 보면 간단한 파싱도 조금 해야 하는 문제가 아닐까 싶습니다.

simm4256   6년 전

소수 오차범위는 앱실론으로 해도 맞던데요...

심지어 오차 생각 안하고 단순 비교만 해도 맞다고 나오던데 이쪽은 데이터가 약한거 같네요

아래는 제가 정답을 맞은 소스입니다. 앱실론 부분을 제거해도 AC가 나오는 코드에요

simm4256   6년 전

엡실론을 쓰지 않으면 위 코드가 틀리는 예제를 만들고 싶지만 어떻게 예제를 짜야 할지 감이 안오네요...

혹시 고수님께서 이 글을 보신다면 위 코드에서 엡실론을 비교하는 부분을 제거하면 틀리도록 할 예제를 만들어주셨으면 좋겠습니다.

simm4256   6년 전

아, 23줄의 sort는 무시하셔도 됩니다. 정렬할 필요가 없는데 실수네요.

chogahui05   6년 전

간단하게 반례 하나 들어드리겠습니다.

한 명의 위치가 105입니다. 속도가 7입니다. 5.3232초가 지난 후에는 우측으로 37.2624만큼 갑니다.

따라서 105 + 37.2624 = 142.2624까지 갈 수 있겠죠?


다른 한 명의 위치는 3432입니다. 속도는 618이고요.

T초가 지나면 3289.7376만큼 갈 수 있겠네요.

3432에서 3289.7376을 빼면 142.2624가 나오죠? 이 두 명은 142.2624에서 만나네요.


테스트 케이스가 허술한 게 맞네요.

홍수가 터지는 시점과 친구들이 만나는 시점이 일치한다면 홍수에 떠내려가기 전에 만날 수 있는 것으로 간주한다.

라고 문제에서 명시했고. 이 경우 정확히 5.3232초 후에 두 명이 만나게 되므로 친구들이 모두 만날 수 있게 됩니다.

제가 잘못 이해했다면 추가 댓 달아주세요.

chogahui05   6년 전

이거 생각보다 굉장히 어려운 문제입니다. 봄을 맞이 해서 이런 문제가 나오다니..

출제진 분이 코너 케이스를 제대로 TC에 안 넣으신 걸로 봐서는..

생각보다 굉장히 어렵고 까다로운 함정이 있는 문제입니다.


기하쪽 알고리즘 할 때 소숫점 오차가 상당히 골때린다던데요. 이 문제도 상당히 골때리네요.

simm4256   6년 전

제시하신 예시는 엡실론으로도 처리가 안되는 차이네요...

소수점이 4자리까지니까 4자리를 따로 저장하는 식으로 해야만 맞는 코드겠군요

일단 TC 추가요청 하겠습니다.

chogahui05   6년 전

네. 왜 그런지는 정확히 잘 모르겠지만, 엡실론으로도 처리가 안 되네요.

보통은 잘 되는 듯 싶은데요. 위 케이스에서는 안 됩니다. 제시한 케이스가 끝점에서 걸치는 경우거든요.


실수형에서 == 비교를 해야만 올바른 답이 나오게끔 한 TC를 작성하다 보니 저런 게 나오더라고요.

예를 들어서 2.3- 와 2.3+


소숫점 x 좌표에서 만나도록 TC를 만들었고요.

문제의 설명대로라면 저 데이터는 답이 0이 아니라 1이 나와야 됩니다.


반례를 찾는 건 어려운데요.

극단적인 케이스를 만들어 보시는 게 그나마 쉬운 방법이 아닐까 싶습니다.

simm4256   6년 전

일단 TC 추가요청은 올렸습니다.

그리고 생각해봤는데 그냥 T에다가 1e4 곱해줘서 전부다 정수로 처리하면 쉬워지네요.

어차피 최대 범위가 1e9라 거기에 1e4 곱해봤자 1e13이니 long long으로 처리가 가능해지니..

다음과 같은 코드로 하면 모든 경우에 대해 맞을 것 같습니다.

songgj123   6년 전

1e4를 곱해서 풀었는데도

오답이 나와서 뭐가 문젠가 했더니

t를 float으로 하면 오답이고

double로 해야 정답이 나오네요....

float으로 하면 3번째 예제 t * 1e4가

23331이 나오게 되네요

한참 헤맷네요

무튼 도움 감사합니다

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