알고리즘

[백준] DP - 2225번, 합분해(다른 풀이 봄)

2023. 11. 11. 23:41
728x90
반응형

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

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

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

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

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


풀이

1. 테이블 정의

  • dp[k][n] = k개의 수를 더해 n을 만들 수 있는 경우의 수

 

2. 점화식

0~N까지의 숫자가 K개 주어진다는 상황을 가정해보자.

N = 마지막 값 + 이전 값들의 누적

점화식으로 적으면, DP[k][n] = DP[k-1][0] + .. + DP[k-1][n] 이다.

 

k (하단) / n 0 1 2 3
1 dp[1][0] = 1 dp[1][1] = 1 dp[1][2] = 1 dp[1][3] = 1
2 dp[2][0] = 1 dp[2][1] = 2 dp[2][2] = 3 dp[2][3] = 4
3 dp[3][0] = 1 dp[3][1] = 3 dp[3][2] = 6 dp[3][3] = 10

 

위의 내용을 코드로 바꾸면 3중 for문으로 작성하게 된다.

더 나은 방식이 없을까?

있다.

 

위의 표 내용을 자세히 보자.

기존의 생각이 전체 값을 더한다는 것이었다면,

이제는 필요한 값만 더해온다는 관점으로 바라보자.

 

dp[2][2]를 2가지로 표현해 볼 것이다.

1) dp[1][0] + dp[1][1] + dp[1][2]

k (하단) / n 0 1 2 3
1 1 1 1 1
2 1 2 3 4
3 1 3 6 10

기존 관점과 동일하다. 표시한 파란색 값을 다 더해야 빨간색 값이 나온다.

 

2) dp[2][1] + dp[1][2]

k (하단) / n 0 1 2 3
1 1 1 1 1
2 1 2 3 4
3 1 3 6 10

 

dp[2][1] = dp[1][0] + dp[1][1]

그러므로, dp[2][2] = dp[2][1] + dp[1][2] 로 대체하여 표현할 수 있는 것이다.

 

따라서 최종 점화식은 다음과 같다.

dp[k][n] = dp[k-1][n] + dp[k][n-1]

 

 

3. 초기값

  • n = 0, dp[k][n] = 1 →dp[k][0] = 1
  • k = 1, dp[k][n] = 1 →dp[1][n] = 1

 

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[][] dp = new int[k+1][n+1];

        for(int i=0; i<k+1; i++) {
            dp[i][1] = i;
        }
        for(int i=0; i<n+1; i++) {
            dp[1][i] = 1;
        }
        for(int i=2; i<k+1; i++) {
            for(int j=2; j<n+1; j++) {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])% 1000000000;
            }
        }
        br.close();
        bw.write(String.valueOf(dp[k][n]));
        bw.flush();
        bw.close();
    }
}

파도반 수열 문제 풀고, 아 이제 좀 성장했나 싶었는데 바로 막혔다.

난이도 보니까 골드Ⅴ 문제였다. 흑.

열심히 해야겠다는 다짐을 오늘도 한다.

 

작다고만 생각말고 작은 생각을 매일 키워라.

 

 


[참고] https://hongjw1938.tistory.com/63  (풀이 정말 좋다!)

https://computer-choco.tistory.com/545  (위의 내용을 이해시켜주는 좋은 풀이!)

저작자표시 비영리 (새창열림)

'알고리즘' 카테고리의 다른 글

[백준] DP - 9461번, 파도반 수열  (0) 2023.11.06
[백준] 정렬 - 11004번, k번째 수 (quicksort로 풀 수 있을까?)  (1) 2023.11.04
[백준] DP - 2133번, 타일 채우기 (다른 풀이 봄)  (1) 2023.11.03
[백준] DP - 1699번 제곱수의 합(다른 풀이 봄)  (1) 2023.11.02
[백준] DP - 2579번, 계단 오르기 (다른 풀이 도움)  (0) 2023.10.27
'알고리즘' 카테고리의 다른 글
  • [백준] DP - 9461번, 파도반 수열
  • [백준] 정렬 - 11004번, k번째 수 (quicksort로 풀 수 있을까?)
  • [백준] DP - 2133번, 타일 채우기 (다른 풀이 봄)
  • [백준] DP - 1699번 제곱수의 합(다른 풀이 봄)
hatch
hatch
250x250
hatch
차근차근 쌓아올리는,
hatch
전체
오늘
어제
  • 분류 전체보기 (121)
    • TIL (3)
    • [JAVA] (17)
      • 생활코딩 (11)
    • 모바일 (25)
      • android (24)
      • ReactNative (1)
    • 웹개발 (25)
      • React (3)
      • jQuery (5)
      • Springboot (2)
    • 알고리즘 (42)
    • [프로그래밍기초지식] (1)
    • [기술문서 읽기] (0)
      • 개념 번역 (0)
    • 인사이트(insight) (2)
    • git (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • write
  • manger

공지사항

인기 글

태그

  • 중복리니어레이아웃
  • javascript
  • state
  • BufferedReader
  • Doit!자바프로그래밍입문
  • 반복문
  • DP
  • 모프2주차
  • scanf
  • 210908
  • 재귀
  • 안드로이드프로그래밍6판
  • 백준
  • jquery
  • 깊은복사
  • 명시적 인텐트
  • 노이클립스
  • TIL
  • 별찍기
  • 타일링

최근 댓글

최근 글

hELLO · Designed By 정상우.
hatch
[백준] DP - 2225번, 합분해(다른 풀이 봄)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.