14488번 - 준오는 급식충이야!!
저는 노가다로 풀었습니다.
간단하게 말하자면 부등식의 교집합 구하는 건데요.
사실 acm icpc의 예선 문제인 교차점과 비슷한 식으로 접근하면 풀리긴 하더라고요.
각 사람마다 갈 수 있는 범위가 있습니다.
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)의 알고리즘이 나옵니다.
제가 윗 댓에서도 말했다 시피 소수 오차가 생각보다 많이 골때립니다.
이 문제 같은 경우는 꽤 정밀해야 해서.. 단순히 엡실론을 이용해서 쓰는 게.. 어려울 듯 싶고요.
링크 건 문제도 같은 이유로 난이도에 비해 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이 소수부가 되는 것이죠.
어떻게 보면 간단한 파싱도 조금 해야 하는 문제가 아닐까 싶습니다.
간단하게 반례 하나 들어드리겠습니다.
한 명의 위치가 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초 후에 두 명이 만나게 되므로 친구들이 모두 만날 수 있게 됩니다.
제가 잘못 이해했다면 추가 댓 달아주세요.
이거 생각보다 굉장히 어려운 문제입니다. 봄을 맞이 해서 이런 문제가 나오다니..
출제진 분이 코너 케이스를 제대로 TC에 안 넣으신 걸로 봐서는..
생각보다 굉장히 어렵고 까다로운 함정이 있는 문제입니다.
기하쪽 알고리즘 할 때 소숫점 오차가 상당히 골때린다던데요. 이 문제도 상당히 골때리네요.
네. 왜 그런지는 정확히 잘 모르겠지만, 엡실론으로도 처리가 안 되네요.
보통은 잘 되는 듯 싶은데요. 위 케이스에서는 안 됩니다. 제시한 케이스가 끝점에서 걸치는 경우거든요.
실수형에서 == 비교를 해야만 올바른 답이 나오게끔 한 TC를 작성하다 보니 저런 게 나오더라고요.
예를 들어서 2.3- 와 2.3+
소숫점 x 좌표에서 만나도록 TC를 만들었고요.
문제의 설명대로라면 저 데이터는 답이 0이 아니라 1이 나와야 됩니다.
반례를 찾는 건 어려운데요.
극단적인 케이스를 만들어 보시는 게 그나마 쉬운 방법이 아닐까 싶습니다.
댓글을 작성하려면 로그인해야 합니다.
songgj123 6년 전 1
이진 탐색으로 풀었습니다.
mid에 왼쪽 사람과 오른쪽 사람 모두 닿지 못하면 0을 반환합니다.
mid를 어느 쪽으로 옮겨도 한 명 이상은 닿지 않기 때문입니다.
오른쪽 사람만 닿지 못하면, mid를 오른쪽으로 옮기고
왼쪽 사람만 닿지 못하면, mid를 왼쪽으로 옮깁니다.
이 방법이 정답이라고 생각하고, 예제도 정답이 나오는데
자료형 때문인지, 반복문 조건 때문인지
오답이 나옵니다.
왜 그럴까요??