[호붕싸 모각코 5차] beakjoon 2225. 합분해

작성자	김윤희
소 감	오늘은 백준 알고리즘 문제를 풀었다. 알고리즘 문제 해결이다보니 친구들과 토론하거나 질문하기보다는 혼자서 집중하여 푸는 시간이였던 것 같다. 하지만 문제가 잘 해결되지 않아 집중력을 잃어갈 때, 옆에서 집중하며 공부하는 친구들이 많은 도움이 되었던 날이다.
일 시	2025. 3. 24. (월) 18:00 ~ 21:00
장 소	미래관 429호 자율주행스튜디오
참가자 명단	신수민, 임혜진, 배세은, 김윤희 (총 4명)
사 진

 

 

2225. 합분해 

문제 설명 

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

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

 

입력 

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

 

출력 

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

 

 

처음 문제를 접할 때, 알고리즘 분류 카테고리를 모르고 접하였다. dp를 사용해야겠다는 생각이 처음부터 들진 않아 방향성을 찾는데 조금 해맸던 문제였다. 

 

나는 위와 같은 사고 과정을 통해 dp라는 것을 알아내고 코드로 구현하게 되었다. 

 

def sumdecompose(n, k):
    dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
    
    for i in range(n+1):
        dp[i][1] = 1 
    
    for i in range(k+1):
        dp[1][i] = i

            
    for i in range(2, n+1):
        for j in range(1, k+1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[n][k] % int(1e9)
    
n, k = map(int, input().split())

print(sumdecompose(n, k))

 

코드 설명 

1. dp 테이블 초기화 및 초기설정 

이때, 어떤 숫자 i를 1개의 숫자로 만들 수 있는 경우의 수는 항상 1이므로 dp[i][1]을 1로 초기화. 

숫자 1을 k개의 숫자로 나타내는 방법은 k가지이므로 dp[1][k] 는 k로 초기화. 

 

2. dp 점화식 계산 

다른 dp 문제들보다 점화식을 떠올리는데는 생각보다 쉬운 문제라고 생각한다. 

(과정은 위 사진을 참고) 

 

 

개선해야할 점 

 

1. 불필요한 초기화를 제거 

사실 dp[1][k] = k인 부분은 필요가 없다는 것을 리뷰하면서 느꼈다. 

어차피 dp[i][j] = dp[i-1][j] + dp[i][j-1]을 통해 채워지므로 생략이 가능할 것이다. 

 

2. 모듈러 연산을 반복문 안에서 수행하여보기 

현재 return 값에서 모듈러 연산을 한 번만 수행하는데, 계산 도중에도 모듈러 연산을 적용한다면 

오버플로우를 방지하는데 도움이 될 것이라고 생각한다. 

 

3. 공간 최적화 

현재 코드에서는 2 차원 배열을 사용하고 있는데, 사실 dp[i]는 dp[i-1]의 값만 참조하고있으므로 

1차원 배열로도 최적화가 가능할 것이다. 

 

def sumdecompose(n, k):
    MOD = int(1e9)
    dp = [1] * (k+1)  # 1차원 배열로 변경

    for i in range(1, n+1):
        for j in range(1, k+1):
            dp[j] = (dp[j] + dp[j-1]) % MOD  # 모듈러 연산 추가

    return dp[k]

n, k = map(int, input().split())
print(sumdecompose(n, k))

 

개선한다면 코드는 위와 같을 것이다. 

---