ps:problems:boj:19737
목차
Torus Travel
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 19737 |
문제명 | Torus Travel |
레벨 | 실버 1 |
분류 |
수학 |
시간복잡도 | O(1) |
사용한 언어 | Python 3.11 |
제출기록 | 33376KB / 52ms |
최고기록 | 40ms |
해결날짜 | 2023/07/21 |
풀이
- 처음에 토러스의 정의부터 시작해서 각종 용어를 영어로 엄밀하게 정의하는데 머릿속에 그리면서 이해하는것에 꽤 노력이 필요하다. 근데 스크롤을 조금만 내리면 친절하게 그림이 나온다..
- 대충 딱 봐도 최적이 아닐듯한 경로들을 제외하면 (outer road를 지나간다던가 하는..), 대충 최적 경로가 될수 있는 후보들이 보인다. 세로로 한칸 이동하는것을 v, inner road로 한칸 이동하는 것을 i, southern road로 한칸 이동하는 것을 s라고 하면 아래의 후보가 있다
- 1번: v-s-v-i-v-s-v-i-…-v 으로 이동하는 방법 (v를 최소화)
- 2번: v-v-i-v-v-i-…-v-v-i-v 로 이동하는 방법 (s를 안거치는 방법)
- 3번: v-s-v-i-v-v-i-v-v-i-…-v-v-i-v 로 이동하는 방법 (예제 문제의 답으로 주어진 방법. s를 딱 한번만 간다)
- v,i,s의 길이는 l[v], l[i],l[s] = (2*pi*r/4, 2*pi*R/n, 2*pi*(R-r)/n) 이다.
- 각 경로에서 v,i,s의 등장 횟수 c[v], c[i], c[s] 는 각각 아래와 같다
- 1번: (n, (n-1)2, n2)
- 2번: (2n-1, n-1, 0)
- 3번: (2n-3, n-2, 1)
- 이제 각 경로마다 거리를 식으로 표현할 수 있다. 입력을 받으면 1,2,3번 경로의 길이를 각각 계산해서 그중 최솟값을 출력하면 된다. 이렇게만 해도 O(1)에 계산되므로 이렇게 구현하고 끝내는 것이 사실은 현명한 선택이다..
- 하지만.. 좀더 깔끔하게 구현해보고 싶으니 식을 정리해보자. 식을 정리해서 비교하면 어떤 경로가 가장 짧을지는 r,R과는 무관하고 n에 따라서만 결정된다는 것을 알수 있다. 그리고 식을 더욱 잘 정리하면 (사실 꽤나 번거롭다), n==2일때만 2번 경로가 가장 짧고, 나머지는 1번 경로가 가장 짧다는 것을 알수 있다. 이제 n에 따라서 결정되는 최소 경로의 거리를 계산해서 출력해주기만 하면 된다,
코드
"""Solution code for "BOJ 19737. Torus Travel".
- Problem link: https://www.acmicpc.net/problem/19737
- Solution link: http://www.teferi.net/ps/problems/boj/19737
"""
import math
def main():
r, R, n = [int(x) for x in input().split()]
x, y, z = (0, (n - 1), n + n - 1) if n == 2 else (n // 2, (n - 1) // 2, n)
answer = (x * R / n + y * (R - r) / n + z * r / 4) * 2 * math.pi
print(answer)
if __name__ == '__main__':
main()
ps/problems/boj/19737.txt · 마지막으로 수정됨: 2023/07/21 16:20 저자 teferi
토론