티스토리 뷰
문제 링크
https://www.acmicpc.net/problem/2225
2225번: 합분해
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
k가 1인 경우는 n에 상관없이 1가지의 방법밖에 존재하지 않습니다.
n이 1일 때 k가 1이면 1, 2이면 2 ... 식의 방법이 존재합니다.
나머지 n에 대한 방법의 수는 아래의 그림처럼 나타낼 수 있습니다.

그림의 수들에서 규칙을 찾아낼 수 있는데 n과 k는 (n-1, k)일 때의 방법과 (n, k-1)일 때의 방법의 합으로 구할 수 있습니다.

구현 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
using namespace std; | |
int d[201][201]; | |
int main(){ | |
int n, k; | |
cin >> n >> k; | |
for (int i=0;i<=k;i++) | |
d[1][i] = i; | |
for (int i=2;i<=n;i++) | |
for (int j=1;j<=k;j++) | |
d[i][j] = (d[i-1][j] + d[i][j-1]) % 1000000000; | |
cout << d[n][k] << endl; | |
return 0; | |
} |
'Coding Test > 백준' 카테고리의 다른 글
[C++] 백준 11052 - 카드 구매하기 (0) | 2020.08.15 |
---|---|
[C++] 백준 2011 - 암호코드 (1) | 2020.08.14 |
[C++] 백준 9461 - 파도반 수열 (0) | 2020.08.12 |
[C++] 백준 2133 - 타일 채우기 (0) | 2020.08.11 |
[C++] 백준 1699 - 제곱수의 합 (0) | 2020.08.10 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- HiveQL
- import
- 팰린드롬 구하기
- HDFS
- 분할정복
- 외발 뛰기
- microwaving lunch boxes
- hive
- 스파크
- Sqoop
- 두니발 박사의 탈옥
- C++
- 완전탐색
- 종만북
- 삼각형 위의 최대 경로 수 세기
- 배열과 문자열
- 백준
- Jaeha's Safe
- 하둡
- Django
- pyspark
- 2225
- 알고스팟
- 합친 lis
- Hadoop
- 삼각형 위의 최대 경로
- 하이브
- 출전 순서 정하기
- 코딩인터뷰 완전분석
- python
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함