🐷전동준(Jeon DongJun)

Go with the flow

[BOJ/백준-Python]11051번 - 이항 계수 2

11051번 - 이항 계수 2

문제

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

입력

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

출력

(\binom{N}{K})를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

5 2

예제 출력 1

10


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

11050번 문제에서 N과 K가 늘어나서 똑같이 재귀함수를 사용해서 풀었더니 재귀초과 에러가 났다. 따라서 다른 풀이방식을 찾아야했고, 아무리 생각해도 모르겠어서 이항계수에 대해서 찾아보니 파스칼 삼각형이라는 것을 알게되었다. 스크린샷 2022-08-02 오후 8 21 30

이렇게 생긴 삼각형으로 위에서부터 아래로 0행, 1행, 2행 순으로 내려간다. 또한 각 행에서 왼쪽에서 오른쪽으로 0열, 1열, 2열 이렇게 늘어난다.

삼각형의 양쪽 빗변은 전부 1이고, 직전 행의 자신의 열과 -1열의 더한 값이 자신의 값이 되는 점을 이용해서 삼각형을 만들어줬다. 리스트 안에 리스트는 각 행을 나타낸다. 이렇게 삼각형을 만들어주고 인덱싱을 사용해 이항 계수를 찾아주고 10007로 나눠주면 문제 해결이다. 파스칼의 삼각형은 여러모로 조합론 쪽에서 많이 쓰일 것 같으므로 잘 기억해야겠다.

코드 💻

import sys

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

triangle = []

for i in range(n+1):
  triangle.append([])
  triangle[i].append(1)

  for j in range(1, i):
    triangle[i].append(triangle[i-1][j-1]+triangle[i-1][j])

  if n > 0:
    triangle[i].append(1)


print(triangle[n][k] % 10007)

해결 로그

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

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] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑