사용자 도구

사이트 도구


ps:problems:boj:9372

상근이의 여행

ps
링크acmicpc.net/…
출처BOJ
문제 번호9372
문제명상근이의 여행
레벨실버 4
분류

기초

시간복잡도O(t*n)
인풋사이즈t<=100, n<=10000
사용한 언어Python
제출기록29200KB / 108ms
최고기록76ms
해결날짜2021/08/03
태그

30단계

풀이

  • 뭔가 이상한 느낌이 들면 정상이다. 사실상 함정문제.
  • N개의 노드를 전부 연결하려면 최소 N-1개의 엣지가 필요하다. 최소 갯수만 출력하면 되므로, 어떤 엣지가 필요한지는 생각할 필요가 없다. 그냥 입력받은 N값에서 -1만 해서 출력하면 된다. 그래서 계산시간은 케이스당 O(1)이지만.. 다음 테스트케이스로 넘어가려면 M줄의 입력을 받아야 하긴 하므로 입력시간까지 고려하면 O(M)이 된다..

코드

"""Solution code for "BOJ 9372. 상근이의 여행".

- Problem link: https://www.acmicpc.net/problem/9372
- Solution link: http://www.teferi.net/ps/problems/boj/9372
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, M = [int(x) for x in sys.stdin.readline().split()]
        for _ in range(M):
            flight = sys.stdin.readline()  # pylint: disable=unused-variable

        print(N - 1)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
D Y N P W
 
ps/problems/boj/9372.txt · 마지막으로 수정됨: 2021/10/24 14:27 저자 teferi