백준5557 - 1학년 (DP) Python

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

문제는 다음과 같이 주어진 요소에 + || - 를 조합하여, 요소 마지막에 나오는 숫자를 만들 수 있는 경우의 수를 구하는 문제다.

 

주어지는 요소의 수가 최대 100개 이하이기 때문에 모든 경우를 직접 모두 구하려면 2^n의 높은 시간복잡도가 우려되고,

왼쪽부터 계산할 때 0 미만 | 20 초과의 수는 포함하지 않기 때문에 다이나믹 프로그래밍을 활용하여 풀이하였다.

 

풀이 과정은 다음과 같다.

앞서 얘기했던 것처럼 0 이상 | 20 이하의 수만 사용하기 때문에, 

다이나믹 프로그래밍으로 메모리제이션할 내용들은 아래와 같은 형식으로 담을 수 있다.

dp = [[0] * 21 for _ in range(N-1)]

즉, 0 ~ 20 까지의 나오는 경우의 수를 N-1 만큼 저장할 수 있는 이차원 배열이다. 

(크키가 N-1인 이유는 결괏값인 N-1까지 + || - 연산을 사용해 값을 구할 필요가 없기 때문에 N-1로 설정했다.)

이는 '경우의 수'만 중복 없이 저장하는 방식으로, 불필요한 중복 연산을 막을 수 있다는 특징을 가진다.

 

이제 위에 만들어 둔 dp를 활용하면 된다.

만약 예제 1번과 같이 arr = [8, 3, 2, 4, 8, 7, 2, 0, 8, 8]의 요소가 있다고 한다면,

마지막에 위치한 '8'은 이전 요소를 조합하여 만들어야 할 결괏값이기 때문에 먼저 제외한 뒤 계산한다.

 

이후 dp[0][arr[0]] = 1 로 초깃값을 설정해줄 수 있는데,

이는 아래와 같이 dp[0]의 요소 중 8의 갯수가 1이라는 의미다.

dp[0] # [0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0]

 

그리고 해당 dp[0]을 순회하며 dp[1]을 구할 수 있다.

순회하는 인덱스를 j로, 다음 숫자를 arr[1] == 3 이라고 표현할 때, dp[0][j] != 0 일 경우에,

아래와 같이 메모라이징을 추가할 수 있게 된다.

# j + arr[1]의 연산이 0 이상, 20 이하면 // j + arr[1] == 11
dp[1][11] += dp[0][8]

# j - arr[1]의 연산이 0 이상, 20 이하면 // j - arr[1] == 5
dp[1][5] += dp[0][8]

dp[1] # [0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0]

이후 이를 반복하여 연산을 진행한 뒤, 이전에 미리 빼둔 결괏값으로 마지막 dp 배열에서 정답을 찾으면 된다.

 

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  N = int(data.pop(0))
  arr = list(map(int, data[0].split()))
  dp = [[0] * 21 for _ in range(N-1)]
  expect = arr.pop()
  dp[0][arr[0]] = 1
  
  for i in range(len(arr) - 1) :
    for j in range(len(dp[i])) : 
      if dp[i][j] != 0 :
        if 0 <= j + arr[i+1] <= 20 : dp[i+1][j + arr[i+1]] += dp[i][j]
        if 0 <= j - arr[i+1] <= 20 : dp[i+1][j - arr[i+1]] += dp[i][j]
  
  print(dp[-1][expect])
  
solution(input_data)