ygreenb
yellowgreenblue
ygreenb
전체 방문자
오늘
어제
  • TIL (130)
    • Algorithm & Data Structure (70)
      • 이론 (4)
      • 프로그래머스 (54)
      • 백준 (12)
    • JAVA (4)
    • Android Studio (9)
    • Database (1)
    • WEB (25)
      • HTML+CSS (7)
      • Javascript (5)
      • React (11)
      • Django (1)
      • Node.js (1)
    • Computer Vision (13)
    • Git (8)

블로그 메뉴

  • HOME
  • TAG
  • GITHUB

공지사항

인기 글

태그

  • 안드로이드
  • 해시
  • Arrays.sort()
  • getOrDefault
  • sort
  • 백준
  • git
  • kotiln
  • 코틀린
  • 스택/큐
  • 깃허브
  • java
  • Android
  • 프로그래머스
  • entrySet
  • 깃
  • React
  • Queue
  • stack
  • PriorityQueue
  • BFS
  • git bash
  • dfs
  • 프로그래머스 Lv.2
  • greedy
  • Comparator
  • HashMap
  • compareTo()
  • DP
  • reactjs

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
ygreenb

yellowgreenblue

[JAVA] 백준 2225번 : 합분해
Algorithm & Data Structure/백준

[JAVA] 백준 2225번 : 합분해

2020. 5. 8. 18:08
 

2225번: 합분해

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

www.acmicpc.net

 

문제

- 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램

- 덧셈의 순서가 바뀐 경우 다른 경우로 셈(1+2와 2+1은 다른경우)

- 한 개의 수를 여러번 쓸 수 있다.

 

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)

 

출력

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

 

 

풀이

만약 입력에 5, 3가 주어졌다고 가정했을 때, 생각할 수 있는 경우의 수는 아래와 같다.

5 = 0 (2번 더해서 0이 되는 경우)+ 5
5 = 1 (2번 더해서 1이 되는 경우)+ 4
5 = 2 (2번 더해서 2이 되는 경우)+ 3
5 = 3 (2번 더해서 3이 되는 경우)+ 2
5 = 4 (2번 더해서 4이 되는 경우)+ 1 
5 = 5 (2번 더해서 5이 되는 경우)+ 0

 

우리가 구해야 하는 경우의 수를 DP[K][N]이라고 하면,

DP[3][5] = DP[2][0] + DP[2][1] + DP[2][2] + DP[2][3] + DP[2][4] + DP[2][5] 가 된다. 

 

즉, 점화식으로 표현한다면 DP[K][N] = DP[K-1][0] + DP[K-1][1] + … + DP[K-1][N] 일 것이다.

 

좀 더 알기 쉽게 표로 나타내면

이런 식인데 보다보면 계속 반복되는 합을 이용하는 걸 알 수 있다.

K=1, N=0인 경우를 제외하면, DP[K][N]에 대하여 아래의 식을 나타낼 수 있다.

 

DP[K][N] = DP[K][N-1] + DP[K-1][N] 

 

이 점화식을 이용하여 코드를 작성하면 아래와 같다.

 

public class bj2225 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		int n = s.nextInt(); // n 입력받음
		int k = s.nextInt(); // k 입력받음
		
		int[][] dp = new int[201][201]; // k번 더해서 n이 되는 경우의 수
		
		for(int i=1;i<=k;i++) {
			dp[i][0]=1;
		}
		for(int i=1;i<=k;i++) {
			for(int j=1;j<=n;j++) {
				dp[i][j] = (dp[i][j-1] + dp[i-1][j])%1000000000; // 1000000000으로 나누는 걸 출력할 때 주면 틀렸다고 뜸.
			}
		}
		System.out.println(dp[k][n]);
	}

}

처음에는 println문에 1000000000을 나눠줬는데 틀렸다고 떠서 나중에 for문 안으로 옮겼다.

오버플로우 때문인듯?

'Algorithm & Data Structure > 백준' 카테고리의 다른 글

[JAVA] 백준 14501번 : 퇴사  (0) 2020.05.16
[JAVA] 백준 1932번 : 정수 삼각형  (0) 2020.05.15
[JAVA] 백준 2293번 : 동전 1  (0) 2020.05.08
[JAVA] 백준 9461번 : 파도반 수열  (0) 2020.05.08
[JAVA] 백준 11726번 : 2Xn 타일링  (0) 2020.05.08
    'Algorithm & Data Structure/백준' 카테고리의 다른 글
    • [JAVA] 백준 1932번 : 정수 삼각형
    • [JAVA] 백준 2293번 : 동전 1
    • [JAVA] 백준 9461번 : 파도반 수열
    • [JAVA] 백준 11726번 : 2Xn 타일링
    ygreenb
    ygreenb
    개발공부기록장

    티스토리툴바