문제 링크
문제 요약
N개의 공항이 원형으로 등 간격 배치되어 있으며, 인접 공항 간의 거리는 D입니다. 두 비행기(비행기 1, 비행기 2)가 이 공항들을 순찰하며 모든 N개의 공항을 정확히 한 번씩 방문해야 합니다.
초기 상태: 두 비행기는 모두 0번 공항에서 시작하며, 이 공항은 이미 방문한 것으로 간주합니다.
비행 규칙:
- 비행 순서: 비행기 1이 먼저 비행을 완료한 후, 비행기 2가 비행을 완료하고, 다시 비행기 1이 비행하는 식으로 교대로 진행됩니다. 이 과정은 각 비행기가 모든 N개의 공항을 방문할 때까지 반복됩니다.
- 비행기 1: 현재 위치에서 시계 방향으로
ap1개의 공항 위를 착륙하지 않고 비행합니다. 그 후, 자신의 비행기가 아직 방문하지 않은 첫 번째 공항에 착륙합니다. - 비행기 2: 현재 위치에서 반시계 방향으로
ap2개의 공항 위를 착륙하지 않고 비행합니다. 그 후, 자신의 비행기가 아직 방문하지 않은 첫 번째 공항에 착륙합니다.
구해야 할 것:
- 각 비행기가 총 이동한 거리 (공항 간 거리 D를 곱한 실제 거리)
- 두 비행기가 동일한 시점에 동일한 공항에 위치한 횟수 (이를 ‘만남’이라고 정의하며, 초기 위치도 포함)
- 두 비행기가 교차한 횟수 (한 비행기가 비행 중에 다른 비행기가 그 공항에 착륙해 있는 경우. 단, 동시에 착륙한 경우는 포함하지 않음)
풀이
이 문제는 주어진 비행 규칙에 따라 두 비행기의 움직임을 시뮬레이션하고, 각 비행기의 이동 거리, 만남 횟수, 교차 횟수를 정확히 계산해야 합니다.
핵심 아이디어
- 상태 추적: 각 비행기의 현재 위치 (
ap1_pos,ap2_pos), 각 비행기가 방문한 공항을 기록하는 배열 (ap1_check,ap2_check), 그리고 총 이동 거리 (ap1_distance,ap2_distance)를 추적합니다. - 만남 횟수: 초기 위치에서 두 비행기가 함께 있으므로
meet_count를 1로 초기화합니다. 각 비행기가 착륙을 완료한 후, 두 비행기의 위치가 같으면meet_count를 증가시킵니다. - 교차 횟수: 한 비행기가
apX만큼 이동하거나, 착륙할 공항을 찾기 위해 추가 이동하는 모든 단계에서, 해당 비행기의 현재 위치가 다른 비행기의 현재 착륙 위치와 같으면cross_count를 증가시킵니다. 만남과는 달리, 동시에 착륙하는 시점은 교차로 간주하지 않습니다. - 다음 착륙 공항 찾기:
apX만큼 이동한 후,apX_check배열을 확인하여 아직 방문하지 않은 다음 공항을 찾을 때까지 한 칸씩 이동하며apX_distance와cross_count를 업데이트합니다.
시뮬레이션 과정 (제공된 코드를 바탕으로 한 설명)
코드는 N-1번의 반복을 통해 각 비행기가 추가로 N-1개의 공항을 방문하도록 시뮬레이션합니다. (총 N개의 공항 방문, 초기 공항 1개 포함)
초기화:
ap1_pos,ap2_pos는 0으로 초기화됩니다.ap1_check[0] = True,ap2_check[0] = True로 설정됩니다.meet_count = 1로 초기화됩니다.cross_count = 0으로 초기화됩니다.ap1_distance = 0,ap2_distance = 0으로 초기화됩니다.
반복문 (for _ in range(N - 1)):
각 반복마다 비행기 1의 턴과 비행기 2의 턴이 순서대로 진행됩니다.
**비행기 1의 턴 (시계 방향으로 이동)
ap1_d만큼 이동:for i in range(ap1_d)루프를 통해ap1_pos를 시계 방향으로ap1_d번 이동시킵니다. 매 이동마다ap1_distance를 1씩 증가시키고,ap1_pos가ap2_pos와 같아지면cross_count를 1 증가시킵니다.- 다음 미방문 공항 찾기:
while ap1_check[(ap1_pos + 1) % N]:루프를 통해 현재ap1_pos에서 시계 방향으로 다음 칸이 이미 방문한 공항인지 확인합니다. 만약 방문했다면,ap1_pos를 한 칸 더 이동시키고ap1_distance를 증가oo시키며,ap1_pos가ap2_pos와 같아지면cross_count를 1 증가시킵니다. 이 과정은 아직 방문하지 않은 공항을 찾을 때까지 반복됩니다. - 착륙:
while루프가 종료되면, 찾은 미방문 공항으로 최종 착륙합니다.ap1_pos를 한 칸 더 이동시키고ap1_distance를 증가시킵니다. 해당 공항을ap1_check[ap1_pos] = True로 방문 처리합니다. - 만남 확인: 착륙 후
ap1_pos와ap2_pos가 같으면meet_count를 1 증가시킵니다.
비행기 2의 턴 (반시계 방향으로 이동)
ap2_d만큼 이동:for i in range(ap2_d)루프를 통해ap2_pos를 반시계 방향으로ap2_d번 이동시킵니다. 매 이동마다ap2_distance를 1씩 증가시키고,ap2_pos가ap1_pos와 같아지면cross_count를 1 증가시킵니다.- 다음 미방문 공항 찾기:
while ap2_check[(ap2_pos - 1 + N) % N]:루프를 통해 현재ap2_pos에서 반시계 방향으로 다음 칸이 이미 방문한 공항인지 확인합니다. 만약 방문했다면,ap2_pos를 한 칸 더 이동시키고ap2_distance를 증가시키며,ap2_pos가ap1_pos와 같아지면cross_count를 1 증가시킵니다. - 착륙:
while루프가 종료되면, 찾은 미방문 공항으로 최종 착륙합니다.ap2_pos를 한 칸 더 이동시키고ap2_distance를 증가시킵니다. 해당 공항을ap2_check[ap2_pos] = True로 방문 처리합니다. - 만남 확인: 착륙 후
ap1_pos와ap2_pos가 같으면meet_count를 1 증가시킵니다.
최종 출력:
모든 시뮬레이션이 끝난 후, ap1_distance * D, ap2_distance * D, meet_count, cross_count를 출력합니다.
정답 코드
"""
[31279: САМОЛЕТИ](https://www.acmicpc.net/problem/31279)
Tier: Bronze 2
Category: implementation, simulation
"""
import sys
from math import sqrt, pi, sin, factorial, ceil, floor
from datetime import datetime, timedelta
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, product
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
from operator import itemgetter, attrgetter, mul, add, sub, truediv
from typing import List, Tuple, Dict, Set, Any, Union
SYS_INPUT = True
RECURSION_LIMIT = 10 ** 7
SET_RECURSION = False
BLANK = " "
if SET_RECURSION:
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda : sys.stdin.readline().rstrip() if SYS_INPUT else input()
mii = lambda : [*map(int,inp().split())]
mfi = lambda : [*map(float,inp().split())]
ii = lambda : int(inp())
fi = lambda : float(inp())
isplit = lambda : inp().split()
p = print
def gcd(a, b): return gcd(b, a % b) if b > 0 else a
def lcm(a, b): return a * b // gcd(a, b)
def solve():
N, D, ap1_d, ap2_d = mii()
ap1_distance = 0
ap2_distance = 0
meet_count = 1
# 두 비행기가 동일한 시점에 동일한 공항에 위치한 횟수 (이를 ‘만남’이라고 정의함). 초기 위치도 포함됩니다.
cross_count = 0 # 두 비행기가 교차한 횟수
# (한 비행기가 어떤 공항을 비행 중에 다른 비행기가 그 공항에 착륙해 있는 경우). 단, 동시에 착륙한 경우는 포함하지 않습니다.
ap1_check = [False] * N
ap2_check = [False] * N
ap1_pos = 0
ap2_pos = 0
ap1_check[ap1_pos] = True
ap2_check[ap2_pos] = True
for _ in range(N - 1):
# 비행기 1 이동
for i in range(ap1_d):
ap1_pos += 1
ap1_distance += 1
ap1_pos %= N
if ap2_pos == ap1_pos:
cross_count += 1
while ap1_check[(ap1_pos + 1) % N]:
ap1_pos += 1
ap1_distance += 1
ap1_pos %= N
if ap2_pos == ap1_pos:
cross_count += 1
ap1_pos = (ap1_pos + 1) % N
ap1_distance += 1
ap1_check[ap1_pos] = True
if ap1_pos == ap2_pos:
meet_count += 1
# 비행기 2 이동
for i in range(ap2_d):
ap2_pos = (ap2_pos - 1 + N) % N
ap2_distance += 1
if ap1_pos == ap2_pos:
cross_count += 1
while ap2_check[(ap2_pos - 1 + N) % N]:
ap2_pos = (ap2_pos - 1 + N) % N
ap2_distance += 1
if ap1_pos == ap2_pos:
cross_count += 1
ap2_pos = (ap2_pos - 1 + N) % N
ap2_distance += 1
ap2_check[ap2_pos] = True
if ap1_pos == ap2_pos:
meet_count += 1
print(ap1_distance * D, ap2_distance * D, meet_count, cross_count)
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()