백준 알고리즘 5557. 1학년

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

5557번: 1학년

 

전체 코드

n = int(input())

dp = [[0 for _ in range(21)] for _ in range(n)]
# dp[i][j] -> i번째 숫자까지 고려했을 때, 합이 j가 되는 경우의 수

arr = list(map(int, input().split()))

# 첫번째 수 저장
dp[0][arr[0]] = 1

# 마지막 숫자를 제외하고 순회
for i in range(1, n - 1):
    for j in range(21):  # 모든 경우의 수에 대해
        if dp[i - 1][j]:  # 이전 단계에서 j값을 만들 수 있는 경우의 수가 있다면
            # 숫자를 더했을떄 범위 내에 있다면
            if 0 <= j + arr[i] <= 20:
                dp[i][j + arr[i]] += dp[i - 1][j]
            # 숫자를 뺐을때 범위 내에 있다면
            if 0 <= j - arr[i] <= 20:
                dp[i][j - arr[i]] += dp[i - 1][j]

# 입력받았던 숫자 중 마지막 숫자와 일치하는 경우의 수가 얼마인지 출력
print(dp[n - 2][arr[-1]])

 

풀이

다음과 같은 DP 테이블을 생성한다. 숫자의 범위는 0~20이며 이를 column으로 설정한다. 제공되는 숫자 n 길이를 기준으로 row를 설정한다.

첫 row의 column은 arr[0]을 인덱스로 하며 1로 초기화한다.

row 인덱스는 1~n-1 범위로 순회한다. col은 0~20 범위로 순회를 진행한다. 순회 중 이전 row에 값이 존재하는 경우 0 =< j + arr[i] <= 20 범위라면  dp[i][j+arr[i]], dp[i][j-arr[i]] 위치에 해당 값을 더한다.

 

만약 범위에서 벗어나면 dp 테이블에 기록되지 않는다.

동일한 부분이 만나게 되면 해당 경우의 수가 동시에 존재했다는 의미이다. 이 경우 숫자를 더해준다.

이렇게 쭉 진행하면 0~20까지 더하기, 빼기 중 발생되는 숫자가 누적된다. 마지막 숫자 arr[-1]와 일치하는 숫자의 개수는 dp[n-2][arr[-1]]을 통해 접근하여 가져올 수 있다.

회고

DP 테이블을 사용하여 접근한다는 생각 자체를 못했다. 0-1 배낭문제처럼 테이블을 순차적으로 타뷸레이션을 진행하는데 바로 떠올리기 쉽지 않았다.

이 문제와 0-1 배낭 문제의 공통점이라면 '모든 경우의 수'를 구한다는 점이고, 숫자의 범위가 주어진다는 점이다. 다이나믹으로 푸는 문제임을 확인했다면 arr의 인덱스를 행으로 만들고, 숫자 범위를 열로 생성한 후 순차적으로 누적시켜 계산하는 것으로 접근해야한다.