[Python][백준 5557][DP] 1학년 - 컴도리돌이

반응형

5557번: 1학년

---

풀이 과정

1. n이 100개라고 브루트 포스로 풀면 안 된다.. 100개의 데이터가 나올 경우, 나올 수 있는 가지 수가 2^99가 나온다. 이 문제는 dp문제로 문제에서 주어진 0보다 크거나 같고 20보다 작거나 같은 조건을 이용해서 해결해야 한다.

2. dp의 크기를 21으로 할당해준다. 그리고 주어진 배열(arr)의 첫 번째 인덱스의 값을 dp의 인덱스에 1로 설정한다. 첫 번째 숫자는 반드시 포함되어야 하기 때문에!!

3. 이중 반복문을 사용하였다. 첫번째 반복문에서는 주어진 배열의 모든 값을 순차적으로 진행시킨다. 그리고 tmp라는 배열을 21 크기로 할당해주었다. dp를 처음부터 2차원 배열로 할당해주면 tmp라는 것은 필요 없는데,, 깔끔해 보이지 않아서 1차원으로 해결하려고 tmp라는 배열을 생성했다.

4. 두번째 반복문은 0부터 20 범위로 진행되는데 arr에 있는 값 i와 0과 21 사이의 값 j를 더하고 뺏을 때 0 이상 20 이하 일 경우 dp의 경우의 수를 더해준다. 

5. dp 배열을 tmp 배열로 교체한다.

6. arr 배열의 마지막 값을 인덱스 end의 dp 값을 출력시킨다.

---

풀이 코드

n,start,*arr,end=map(int,open(0).read().split())
dp = [0]*21 ; dp[start] = 1
for i in arr:
  tmp = [0] * 21
  for j in range(21):
      if i+j <= 20:tmp[j+i]+=dp[j]
      if j-i >= 0 :tmp[j-i]+=dp[j]
  dp = tmp
print(dp[end])