조합 (DP)
📍 조합 (C)
순서 고려 X. 뽑기만
- r ! → 순서가 다른 경우의 수 제거
- 동적 계획법 → 점화식
- 파스칼의 삼각형
📍 점화식 세우는 과정
1. 특정 문제 가정
2. 모든 부분 문제가 해결된 상황이라 가정하고 지금 문제 생각
3. 특정 문제 해결한 내용 바탕으로 일반 점화식 도출
📍 예제
[백준/JAVA] 16395번: 파스칼의 삼각형
📖 문제 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은
bono039.tistory.com
[백준/JAVA] 11050번: 이항 계수 1
🔺 문제 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 import jav
bono039.tistory.com
[백준/JAVA] 11051번: 이항 계수 2
🔺 문제 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 import
bono039.tistory.com
[백준/JAVA]2775번: 부녀회장이 될테야
🔺 문제 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 🔺 코드 1 2 3 4
bono039.tistory.com
[백준/JAVA] 1010번: 다리 놓기
🔺 문제 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이
bono039.tistory.com
(참고)
파스칼의 삼각형 - 조합
파스칼의 삼각형 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 파스칼의 삼각형 속의 숫자들은 바로 윗 줄에 인접하는 두 숫자의 합으로 정의된다. 파스칼의 삼각형(Pascal's triangle)은 수학에서 이항계수를 삼각형 모양으로
ko.wikipedia.org