사용자 도구

사이트 도구


ps:problems:boj:1010

다리 놓기

ps
링크acmicpc.net/…
출처BOJ
문제 번호1010
문제명다리 놓기
레벨실버 5
분류

기초

시간복잡도O(T*n)
인풋사이즈T<=???, n<=30
사용한 언어Python
제출기록31312KB / 116ms
최고기록56ms
해결날짜2021/08/22

풀이

  • 기초적인 조합론으로 답이 C(M,N)이 되는것을 쉽게 알수 있다. 이항계수 C(x,y)는 math.comb를 쓰면 된다
  • 워낙 간단한 문제라서 숏코딩도 한번 건드려봤다. 기존의 파이썬 최고 기록인 78b를 4byte 더 줄여서 최고기록을 74b로 갱신했다.
    • 기존
      • import math
        for l in[*open(0)][1:]:print(math.comb(*map(int,l.split()[::-1])))
    • 갱신
      • import math
        for l in[*open(0)][1:]:print(math.comb(int(l[2:]),int(l[:2])))

코드

"""Solution code for "BOJ 1010. 다리 놓기".

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


def main():
    T = int(input())
    for _ in range(T):
        N, M = [int(x) for x in input().split()]
        print(math.comb(M, N))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
V I G I A
 
ps/problems/boj/1010.txt · 마지막으로 수정됨: 2021/08/22 15:07 저자 teferi