알고리즘

[백준] 2225 합분해 - 골드 5

swanzzz 2025. 5. 26. 22:22
반응형

[오늘의 문제]

https://www.acmicpc.net/problem/2225

[오늘의 학습 키워드]

  • DP
  • 구현

1. 문제설명

 

N개의 정수가 주어질 때 N개의 정수중 K개를 이용하여 합이 N이 되는 경우의 수를 구하는 문제 입니다.

 

예를들어 20 2 가 주어진다면

 

0부터 20까지의 숫자중 2개를 사용하여 20을 만드는 경우의 수를 찾는 문제입니다.

 

같은 숫자를 여러번 사용해도 되고 덧셈의 순서가 바뀐다면 다른 경우로 셉니다.

 

즉 0 + 20 과 20 + 0 은 다른 경우의 수라는 것을 의미합니다.

[제한사항]

  • 시간 제한 2초
  • 메모리 제한 128MB
  • 1 ≤ N ≤ 200
  • 1 ≤ K ≤ 200

2. 접근방식

 

이번 문제는 점화식을 세우기 위해 N과 K의 관계를 잘 살펴보아야 합니다.

 

위 그림에서 N이 어떤 수가 오던간에 K가 1개 즉 1개의 수만을 이용해 N을 만들어야 한다면 무조건 1밖에 올 수 없죠

 

K가 2가 된다면 각 경우의 수는 다음과 같습니다.

K가 2일때 1을 만드는 경우의 수는 0+1, 1+0 으로 두가지 존재하고 2의 경우 0+2, 1+1, 2+0 이 존재하죠

3의 경우 0+3, 3+0, 2+1, 1+2 로 4개가 존재합니다.

 

기존의 경우의 수에 1가지가 추가되죠

 

 

K가 3이 되는 순간 경우의 수가 기하급수적으로 늘어납니다.

 

K가 3일때 1을 만드는 방법은 0 0 1 / 0 1 0 / 1 0 0 이 존재하고

2를 만드는 방법은 0 0 2 / 0 2 0 / 2 0 0 / 0 1 1 / 1 0 1 / 1 1 0 으로 6개가 존재하죠

 

이렇게 보면 하나의 규칙성이 보입니다.

 

 

녹색의 수를 만들기 위해서는 노란색의 수의 합이 필요하죠

 

실제로 경우의 수가 동일한지 예제로 주어진 N = 6, K = 4 를 위의 방식으로 채워보겠습니다.

 

 

이렇게 채우니 예제의 출력 결과가 동일합니다. 여기서 세울 수 있는 점화식은 다음과 같죠

DP[i][j] = DP[i - 1][j] + DP[i][j - 1]

 

위 점화식이 생기게 됩니다. 

 

이를 코드로 구현해 보았습니다.

3. 코드

import sys
input = sys.stdin.readline

# 입력
N, K = map(int, input().split())
# DP 테이블 생성 및 초기화
DP = [[1] * (N + 1) for _ in range(K)]

# 점화식 토대로 누적 경우의 수 계산
for i in range(1, K):
    for j in range(1, N + 1):
        DP[i][j] = DP[i - 1][j] + DP[i][j - 1]

# 정답위치 및 출력조건 맞추기
answer = DP[K-1][N]
print(answer % 1000000000)

[코드설명]

앞선 접근방식을 통해 점화식을 세웠습니다.

 

DP 테이블의 초기화 경우 K가 1이 온다면 N이 어떤 수가 오든 무조건 1밖에 들어가지 못합니다.

 

따라서 DP 테이블을 생성할 때 1로 초기화해서 생성해도 큰 차이가 없죠

 

또한 K의 수에 따라서 N에 생성되는 수가 달라지기 때문에 전체 행렬에서 K번과 N번의 숫자를 맞춰주어야 합니다.

 

K = 1 인 경우 이미 동작이 완료되었고 DP 테이블의 크기를 K까지만 생성했기에 index를 맞추기 위해서 1부터 K까지만 반복을 실시했습니다.

 

이 경우 K가 4가 주어진다면 0을 제외한 1부터 3까지만 반복을 시행하기에 원하던 결과를 맞출 수 있습니다.

 

N의 경우 주어진 2차원 테이블의 열에 해당하니 K행 반복을 시행할 때 채워주어야 하죠

 

앞선 점화식을 토대로 i,j의 위치를 찾아 값을 맞춰 주었습니다.

4. 결과

[회고]

문제를 처음 접근했을때 점화식을 세우기가 굉장히 어려웠습니다.

 

행렬을 이용해 점화식을 세울 생각을 하지 않고 손으로 무작정 모든 경우의 수를 적어가며 경우의 수를 찾아보았죠

 

 

손으로 경우의 수를 작성해가며 풀어보려 하니 도저히 답이 보이지 않았습니다.

 

이렇게는 제대로 파악할 수 없겠다 생각하여 excel을 켜서 조건에 맞춰 식을 세워보는 식으로 변경하였죠

 

점화식을 제대로 파악한 것을 3을 채우는 과정이었습니다.

 

K가 2가 주어지는 경우 이전수 + 1 이라는 식이 나왔었는데 여기까지만 보니 제대로 파악이 되지 않았습니다.

 

K가 3이 주어진 경우 2의 경우의 수가 6으로 뛰었고 3의 경우의 수가 10으로 뛸 때 규칙이 보였습니다.

 

기존수에 이전수를 더한다면 현재의 수가 완성 되더군요 이 조건이 정말로 채워지는지 예제 2번을 검증하며 점화식을 제대로 세웠구나 확신이 들었습니다.

 

또한 이렇게 풀면서 느낀건데 기존 수에 이전 수를 더해주기 때문에 2차원 DP 배열이 아닌 1차원 DP 배열로도 문제가 해결이 가능할 것 같았습니다.

 

기존수는 최초 DP 배열을 초기화 하며 1차적으로 값이 채워지게 되고 중첩 반복문을 이용한다면 기존의 행렬 움직임을 구현할 수 있습니다.

 

1차원 DP 배열에 중첩 반복문을 적용시키려면 DP 배열의 기존값은 이전값의 누적을 구하면 되었고 코드로 작성하면 다음과 같았습니다.

for i in range(K - 1):
	for j in range(1, N + 1):
		DP[j] += DP[j - 1]

 

동일하게 행렬에 대해 중첩 반복문을 통해 동작할 때 1차원 DP 배열을 초기 [1, 1, 1, 1, 1, 1, 1] 로 생성되어 있겠죠

 

여기서 1회 동작을 완료하면 DP 배열을 [1, 2, 3, 4, 5, 6, 7] 로 초기화 될 것입니다.

 

다시 i에 따라서 2회더 동작을 수행하면 기존값에 이전값을 누적하기 때문에 2회 동작시 DP 테이블은 [1, 3, 6, 10. 15, 21, 28] 이 될 것입니다.

 

기존의 [1, 2, 3, 4, 5, 6, 7] 에 각각의 이전수를 더해주기 때문이죠 마지막 동작까지 완료하면 DP 테이블은 [1, 4, 10, 20, 35, 56, 84] 로 수정되겠죠 

 

이렇게 하면 기존의 동작과 동일한데 1차원 DP 테이블로도 문제를 해결할 수 있었습니다.

 

실제로 코드를 수정하여 돌려본 결과 제대로 동작하였습니다.

 

무튼 이번 문제는 점화식을 세우는 과정이 힘들었습니다.


DP 테이블을 1차원으로 생각할지, 2차원으로 생각할지 고민이 많았고 손으로 직접 조건을 확인하며 문제를 풀었을 때 점화식이 제대로 세워지지 않았기 때문입니다.

 

손으로 해결못해 다른 방법을 활용하였고 결국에는 점화식을 세워 문제를 해결할 수 있었죠

 

이번 문제는 고민과 해결에 시간이 오래 걸렸습니다. 약 1시간 조금 넘게 문제를 푸는데 집중했었습니다.

 

조건만 찾는다면 쉽게 해결이 가능한 문제 였는데 그만큼 조건을 찾기가 어려웠습니다.

 

다음 시간에도 DP 문제를 풀어보며 글을 써보겠습니다.

반응형