🐷전동준(Jeon DongJun)

Go with the flow

[BOJ/백준-Python]11050번 - 이항 계수 1

11050번 - 이항 계수 1

문제

자연수 (N)과 정수 (K)가 주어졌을 때 이항 계수 (\binom{N}{K})를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 (N)과 (K)가 주어진다. (1 ≤ (N) ≤ 10, 0 ≤ (K) ≤ (N))

출력

(\binom{N}{K})를 출력한다.

예제 입력 1

5 2

예제 출력 1

10


해결할 방법을 생각해보자.💡

이항계수가 뭔지 몰라서 찾아보니 수학적인 지식이 없으면 어려울 문제였다. 조금 쉽게 생각하려면 조합을 생각해야할 것 같다. 이전에 인적성 문제를 풀었을 때 배운 기억이 있다. nCk의 형태로 표현할 수 있다. 여기서 n은 대상의 수, k는 대상을 고르는 개수라고 생각하자. 예제는 5개중 2개씩 골라 조합을 짜면 몇가지 경우의 수가 생기냐를 뜻하는 것이다.

A, B, C, D, E가 있다고 가정해보자. 그러면 이 중에서 2개씩 뽑아서 조합하는 모든 경우는 다음과 같다.

AB
AC
AD
AE
BC
BD
BE
CD
CE
DE

이렇게 10가지의 경우가 나온다. 이것을 식으로 표현하면 다음과 같다.

n! / (n-k)! k!

이것을 5와 2를 넣어서 풀어보면,

5 * 4 * 3 * 2 * 1 / 3 * 2 * 1 * 2 * 1 이렇게 된다.

여기서 지울 수 있는 것들을 지워주면 5 * 2만 남아 10이 된다.

즉, 팩토리얼을 이용해서 풀 수 있고 팩토리얼은 반복문이나 재귀를 이용해서 함수를 구현할 수 있다.

재귀함수를 사용해서 팩토리얼 함수를 구현해보자.

def fact(n):
    if (n > 1):
        return n * fact(n-1)
    else:
        return 1

이렇게 팩토리얼값을 얻는 함수를 정의했다면, n과 k를 받아주자.

n, k = map(int, sys.stdin.readline().split())

그렇다면 이항계수(조합)을 구하는 식 n! / (n-k)! k!를 코드로 표현해보자. 여기서 나누기 때문에 실수로 변하므로 int를 사용해 정수형으로 변환시킨 후 출력하면 정답이 나올 것이다!

print(int(fact(n) / (fact(n-k) * fact(k))))

코드 💻

import sys

def fact(n):
    if (n > 1):
        return n * fact(n-1)
    else:
        return 1

n, k = map(int, sys.stdin.readline().split())

print(int(fact(n) / (fact(n-k) * fact(k))))

해결 로그

문제 푼 날짜 체크
2022-08-03 ✔
   
   
   
   

2022

[web]jQuery 복습 3

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 2

13 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 1

14 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리4

5 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리3

10 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리2

7 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리1

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]CSS 기초 정리

11 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]HTML 기초 정리

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[Pandas]pandas 연습

3 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑

2021

[Python기초]module

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑