KimMinJun
Coding Note
KimMinJun
전체 방문자
오늘
어제
  • 분류 전체보기 (502) N
    • ALGORITHM (11)
      • 정렬 (6)
      • 최단경로 (1)
      • 자료구조 (1)
      • 슬라이딩 윈도우 (1)
      • etc (2)
    • Git (5)
    • Web (24)
      • Vanilla JS (13)
      • TS (2)
      • React (7)
      • ETC (1)
    • React 공식문서 (번역, 공부) (11)
      • Quick Start (2)
      • Installation (0)
      • Describing the UI (9)
      • Adding Interactivity (0)
      • Managing State (0)
      • Escape Hatches (0)
    • Next.js 공식문서 (번역, 공부) (3)
      • Getting Started (2)
      • Building Your Application (1)
    • PS (432)
      • 백준 (187)
      • Programmers (105)
      • CodeUp (21)
      • STL (3)
      • 제코베 JS 100제 (50)
      • SWEA (0)
      • LeetCode (65)
    • IT (1)
    • Docker (14) N
    • CS (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 관리

공지사항

인기 글

태그

  • 제코베 JS 100제
  • codeup
  • 백준
  • js
  • C++
  • C
  • Level1
  • recursion
  • LeetCode
  • tree
  • Level 2
  • 그래프
  • 정렬
  • 수학
  • Level 0
  • programmers
  • string
  • Level 1
  • 문자열
  • 다이나믹 프로그래밍

최근 댓글

최근 글

hELLO · Designed By 정상우.
KimMinJun

Coding Note

PS/백준

백준 / 다이나믹 프로그래밍 / 2225번 / 합분해 / C++

2021. 8. 30. 23:17

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1 

20 2

예제 출력 1 

21

 

#include <iostream>
using namespace std;

const int N = 201;
const int K = 201;
const int divisor = 1e9; 

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	long long dp[K][N] = {0,};	
	int n, k;
	cin >> n >> k;
	
	for(int i=0; i<=n; i++) {
		dp[1][i] = 1;
	}
	
	for(int i=2; i<=k; i++) {
		for(int j=0; j<=n; j++) {
			for(int l=0; l<=j; l++) {
				dp[i][j] += dp[i-1][l];
			}
			dp[i][j] %= divisor;
		}
	}
	
	cout << dp[k][n] << '\n';
	
	return 0;
}

일단 dp[k][n]는 n을 0부터 n까지의 수중에서 k개의 합으로 나타낼 수 있는 경우를 나타낸다.

n을 수 1개로 나타내는 경우는 무조건 n하나로 나타내는 경우 한가지이기 때문에 dp[1][0...n]을 모두 1로 초기화했다.

 

예시로 dp[2][2]가 있다고 생각해보자.

위의 의미는 0부터 2까지의 수중에서 2개의수로 2를 나타내는 경우의 수이다.

 

0 + 2 = 2

1 + 1 = 2

2 + 0 = 2

 

위와 같을 것이다.

 

우리는 위의 식이 2개의 수로 2를 만든 식이지만, 아래와 같이 다시 나타낼 수 있다.

 

1개의 수로 0을 나타냄 + 1개의 수로 2를 나타냄 = 2

1개의 수로 1을 나타냄  + 1개의 수로 1을 나타냄 = 2

1개의 수로 2를 나타냄 + 1개의 수로 0을 나타냄 = 2

 

위에서 + 연산자 앞의 항만 따로 뽑아서 생각해본다면 다음과 같이 나타낼 수 있다.

 

dp[1][0]

dp[1][1]

dp[1][2]

 

따라서 우리는 위와같은 결과 도출로 일반항을 얻어낼 수 있는데 아래와 같다.

dp[k][n] = dp[k-1][0] + dp[k-1][1] + ... + dp[k-1][n] 이다.

위의 일반항을 코드로 나타내준다면 풀리는 문제이다.

저작자표시 (새창열림)

'PS > 백준' 카테고리의 다른 글

백준 / 다이나믹 프로그래밍 / 15988번 / 1, 2, 3 더하기 3 / C++  (0) 2021.09.02
백준 / 다이나믹 프로그래밍 / 11053번 / 가장 긴 증가하는 부분 수열 / C++  (0) 2021.08.31
백준 / 다이나믹 프로그래밍 / 1912번 / 연속합 / C++  (0) 2021.08.28
백준 / 다이나믹 프로그래밍 / 2193번 / 이친수 / C++  (0) 2021.08.26
    'PS/백준' 카테고리의 다른 글
    • 백준 / 다이나믹 프로그래밍 / 15988번 / 1, 2, 3 더하기 3 / C++
    • 백준 / 다이나믹 프로그래밍 / 11053번 / 가장 긴 증가하는 부분 수열 / C++
    • 백준 / 다이나믹 프로그래밍 / 1912번 / 연속합 / C++
    • 백준 / 다이나믹 프로그래밍 / 2193번 / 이친수 / C++
    KimMinJun
    KimMinJun

    티스토리툴바