[백준: Python] 18427 - 함께 블록 쌓기

[문제]

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

약간의 제약이 붙은 DP 문제입니다.

 

블록을 하나만 써야 한다는 조건을 신경을 써야 풀이가 가능하겠습니다.

---

[초기화]

    def __init__(self):
        self.n, self.m, self.h = map(int, input().split())
        self.blocks = [list(map(int, input().split())) for _ in range(self.n)]

---

[풀이]

    def solve(self):
        dp = [0] * (self.h + 1)  # dp[x]: 높이가 x인 탑을 만드는 경우의 수
        dp[0] = 1  # 높이 0을 만드는 경우의 수는 1

        for student_blocks in self.blocks:
            next_dp = dp[:]  # 현재 상태를 복사
            for block in student_blocks:
                for height in range(self.h, block - 1, -1):
                    next_dp[height] = (next_dp[height] + dp[height - block]) % 10007

            dp = next_dp  # 업데이트

        print(dp[self.h])

1. 학생들의 블록을 순차적으로 가져옵니다.
2. 현재의 리스트 정보를 복사합니다.
   • 리스트를 복사하는 이유는, 현재 쌓은 블록이 추후 쌓을 블록(나와 다른 학생)에 간섭받을 수 있기 때문입니다.
   • 가령 첫 번째 테스트케이스의 경우, 리스트를 복사하지 않으면 다음과 같은 상황이 발생합니다.
     1. 첫 시작: [1, 0, 0, 0, 0, 0]
     2. 두 번째: [1, 0, 1, 0, 0, 0] → 높이 2의 블록을 쌓음
     3. 세 번째: [1, 0, 1, 0, 0, 1] → 높이 3의 블록을 쌓는 과정에서 높이 2의 블록을 참조하기 때문에 h 블록 갱신
   • 즉 위의 상황에서 보이듯이 한 학생이 자신이 가진 블록을 한 번에 2개 이상 사용하는 상황이 발생하게 됩니다.
3. 복사한 리스트를 기준으로 DP를 수행합니다.
4. 현재 학생의 블록을 다 쌓았다면 리스트를 최종 갱신합니다.

즉 복사하는 이유는, 이전에 쌓은 블록을 사용하지 않기 위해서입니다.

 

그래서 알고리즘 진행 과정에서 실질적으로 사용되는 값은 복사된 값입니다.

---

[전체 코드]

class Main:
    def __init__(self):
        self.n, self.m, self.h = map(int, input().split())
        self.blocks = [list(map(int, input().split())) for _ in range(self.n)]

    def solve(self):
        dp = [0] * (self.h + 1)  # dp[x]: 높이가 x인 탑을 만드는 경우의 수
        dp[0] = 1  # 높이 0을 만드는 경우의 수는 1

        for student_blocks in self.blocks:
            next_dp = dp[:]  # 현재 상태를 복사
            for block in student_blocks:
                for height in range(self.h, block - 1, -1):
                    next_dp[height] = (next_dp[height] + dp[height - block]) % 10007

            dp = next_dp  # 업데이트

        print(dp[self.h])


problem = Main()
problem.solve()

---