[BOJ] [5557] 1학년 (Python)

내 해답)

import sys; ip = sys.stdin.readline

N = int(ip())
nl = list(map(int,ip().split()))
#입력 받기
before = {0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0,10:0,11:0,12:0,13:0,14:0,15:0,16:0,17:0,18:0,19:0,20:0}
after = {0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0,10:0,11:0,12:0,13:0,14:0,15:0,16:0,17:0,18:0,19:0,20:0}
before[nl[0]] = 1
#초기 세팅

for i in range(1,N-1): #N번 반복
  q = [k for k,v in before.items() if v>0] #before에 있는 키들 중 값이 0보다 큰 것들 리스트화
  while q:
    n = q.pop()    #하나씩 추출해서
    if n-nl[i]>=0: #다음 수를 뺀것이 0이상일 때
      after[n-nl[i]] += before[n] #after에 더해줌
    if n+nl[i]<=20:               #다음 수를 더한 것이 20이하일 때
      after[n+nl[i]] += before[n] #after에 더해줌
  before = after.copy()			  #after를 before에 복사
  for k in after.keys():		  #after 값들 0으로 초기화
    after[k] = 0
print(before[nl[-1]]) 			  #결과 (nl 마지막 값을 키로 가지는 item의 값) 출력

나는 N번째 숫자까지 계산한 결과를 기록해놓는다면 N+1번째 숫자를 계산한 결과가 어떻게 될지를 쉽게 알 수 있다는 점을 이용했다. 예를 들어 N번째 숫자까지 계산한 결과가 2(세 번), 8(두 번)이고 N+1번째 수가 3일 경우, 결과가 5(다섯 번) (2에서 5가 된 경우 + 8에서 5가 된 경우), 11(두 번)이 되는걸 알 수 있다.

 

기록하는 자료형으로는 딕셔너리를 사용했다. 예를 들어 i가 24일 때 before[14] 가 4 라면, 24번째 숫자까지 계산을 시뮬레이션했을 때 14라는 숫자가 4번 나왔음을 의미한다. 결국 마지막까지 반복한 이후 nl[-1], 즉 입력의 마지막 숫자를 키(key)로 갖는 아이템(item)의 값(value)이 올바른 등식의 개수가 된다.

 

리뷰)

다이나믹 프로그래밍(DP) 문제로, 재귀를 사용하면 중복 사항에 대한 처리가 힘들며 높은 확률로 시간 초과가 걸리는 문제.

1년 정도만에 다시 본 문제였는데, 변수명도 이상하고 각주가 없어서 해석하는데 좀 걸렸다. 예전의 나는 어떻게 코딩을 한건가 싶다,,,

처음으로 설명한 문제였는데 확실히 머릿속에 있는 걸 논리적으로 꺼내놓기가 쉽지 않다.