내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
공항
ps:problems:boj:10775
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 공항 ====== ===== 풀이 ===== * [[ps:Disjoint Set]]을 이용해서 인접한 숫자들을 그룹으로 묶어서 관리하는 테크닉을 사용하는 문제이다. * 동일한 테크닉을 사용하는 거의 비슷한 문제로 [[ps:problems:programmers:64063]]이 있으니, 테크닉에 대한 설명은 그쪽을 참조. * 시간복잡도는 n이 비행기의 수, m이 게이트의 수 일때, O(m+n*α(m))이 된다 ===== 코드 ===== <dkpr py> """Solution code for "BOJ 10775. 공항". - Problem link: https://www.acmicpc.net/problem/10775 - Solution link: http://www.teferi.net/ps/problems/boj/10775 Tags: [Disjoint Set] """ import sys from teflib import disjointset def main(): G = int(sys.stdin.readline()) P = int(sys.stdin.readline()) g = [int(sys.stdin.readline()) for _ in range(P)] dsu = disjointset.DisjointSet(G) gate_by_set = list(range(G)) for i, g_i in enumerate(g): set_id = dsu.find(g_i - 1) gate = gate_by_set[set_id] if gate is None: answer = i break if gate == 0: gate_by_set[set_id] = None else: prev_gate = gate_by_set[dsu.find(gate - 1)] gate_by_set[dsu.union(gate, gate - 1)] = prev_gate else: answer = P print(answer) if __name__ == '__main__': main() </dkpr> * Dependency: [[:ps:teflib:disjointset#DisjointSet|teflib.disjointset.DisjointSet]] {{tag>BOJ ps:problems:boj:골드_2}}
ps/problems/boj/10775.txt
· 마지막으로 수정됨: 2022/01/13 08:48 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로