💡문제
1번부터 N번까지의 학생들은 각각 블록들을 가지고 있다. 학생마다 최대 M개의 블록을 가지고 있을 수 있으며, 한 명의 학생이 가지고 있는 모든 블록들의 높이는 서로 다르다. 이 때 1번부터 N번까지의 학생들이 가진 블록을 차례대로 사용하여 바닥에서부터 쌓아올려 하나의 탑을 만들고자 한다.
단, 어떤 학생의 블록은 사용하지 않아도 되며 한 학생당 최대 1개의 블록만을 사용할 수 있다.
1번부터 N번까지의 학생들이 가지고 있는 블록들에 대한 정보가 주어졌을 때, 높이가 정확히 H인 탑을 만들 수 있는 경우의 수를 계산하는 프로그램을 작성하시오.
예를 들어 N=3, M=3, H=5일 때, 각 학생마다 가지고 있는 블록들의 높이가 다음과 같다고 가정하자.
- 1번 학생: 2, 3, 5
- 2번 학생: 3, 5
- 3번 학생: 1, 2, 3
이 때, 탑의 높이가 정확히 5가 되도록 블록을 쌓는 경우로는 다음의 6가지가 존재한다. (블록을 사용하지 않는 경우는 X로 표시하였다.)
입력
첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구분되어 주어진다.
단, 모든 블록의 높이는 1,000 이하의 자연수이며 한 명의 학생이 가지고 있는 모든 블록들의 높이는 서로 다르게 주어진다.
출력
첫째 줄에 높이가 H인 탑을 만드는 경우의 수를 10,007로 나눈 나머지를 출력한다.
예제입력
3 3 5
2 3 5
3 5
1 2 3예제출력
6📖내가 작성한 Code
import sys
'''
배낭 문제임
햇갈리지 않게 미리 MOD 변수 설정
'''
MOD = 10007
def knapsack(n, h, array):
dp = [[1] + [0] * h]
for i in range(1, n + 1):
new_dp = dp[i - 1].copy()
for b in array[i - 1]:
for j in range(b, h + 1):
new_dp[j] = (new_dp[j] + dp[i - 1][j - b]) % MOD
dp.append(new_dp)
return dp[n][h]
def main():
inputs = map(str.split, sys.stdin.read().splitlines())
n, m, h = (int(item) for item in next(inputs))
students = [[int(item) for item in next(inputs)] for _ in range(n)]
print(knapsack(n, h, students))
if __name__ == '__main__':
main()✍️풀이과정
전형적인 배낭문제. 연습으로 풀어봄. 혹시 모르겠다면 개념을 다시 보고 오는 것을 추천.
🧠 코드 리뷰
-
읽지 않는 변수 처리 : main() 함수에서 입력으로 받은 변수 m은 이후에 사용되지 않습니다. 만약 m이 문제 풀이에 영향을 주지 않는다면, 읽기만 하고 사용하지 않는다는 점을 주석으로 명시하거나, 입력 형식에 맞춰서 처리 후 무시할 수 있습니다.
-
메모리 최적화 – 롤링 DP (Rolling DP) : 현재 DP 테이블은 각 학생마다 새로운 행을 만들어 dp에 추가하고 있습니다. 만약 최종 결과만 필요하고 이전 단계의 DP 테이블을 참조하지 않는다면, 한 개의 1차원 배열만을 사용해 롤링 DP 기법을 적용할 수 있습니다.
🛠️AI 개선 코드
import sys
MOD = 10007
def knapsack(n, h, array):
# dp[j]: 이전 학생까지 고려하여 합이 j가 되는 경우의 수
dp = [1] + [0] * h
for options in array:
new_dp = dp[:] # 이전 dp 상태를 그대로 복사 (얕은 복사)
# 각 학생의 가능한 옵션(비용) b에 대해 dp 업데이트
for b in options:
# dp 배열은 이전 단계의 상태(dp)에서 값을 가져와 사용하므로,
# forward 혹은 reverse 방식 모두 new_dp를 이용하면 안전함.
for j in range(b, h + 1):
new_dp[j] = (new_dp[j] + dp[j - b]) % MOD
dp = new_dp # 이번 학생까지 고려한 결과로 dp 갱신
return dp[h]
def main():
# m은 사용하지 않으므로 _로 처리
inputs = map(str.split, sys.stdin.read().splitlines())
n, _, h = (int(item) for item in next(inputs))
students = [[int(item) for item in next(inputs)] for _ in range(n)]
print(knapsack(n, h, students))
if __name__ == '__main__':
main()
💻결과
🖱️참고 링크
