[백준-5557] 1학년
풀이
나는 2개의 list를 이용해서 문제를 풀었다. 하나는 i인덱스 까지 계산했을 때 나오는 수들을 인덱스로 하여 값을 i로 하는 리스트이고 이를 dp라고 하겠다.
예를 들어 2번인덱스 까지 계산한 값들이 1,4,5라면 dp[1]=2,dp[4]=2,dp[5]=2이다.
그다음 3번인덱스까지 계산했을 때는 dp[j]=i인 j값들을 찾고(1,4,5) j들에다가 3번인덱스를 더하고 뺀 값을 다시 dp의인덱스로 하여 그값을 3으로 한다.
다른 리스트는 i번 인덱스까지 계산했을 때 나오는 값들의 개수를 저장하고 이 리스트를 dp2라고 하면 위의 예시에서 2번인덱스까지 계산했을 때 dp2[1]=1,dp2[4]=1,dp2[5]=1 이고 나머지는 0이다. 그다음 3번인덱스를 k라고하면
임시로 tmp에다가 개수를 저장하고(tmp[1+k]+=dp2[1]...), dp2=tmp로 바꿔준다.
코드
import sys
input = sys.stdin.readline
n=int(input())
nums=list(map(int,input().split()))
dp=[0]*21
dp2=[0]*21
dp2[nums[0]]=1
for i in range(1,n-1):
tmp=[0]*21
li=[]
for j in range(0,21):
if dp[j]==i-1:
if j+nums[i]<=20:
li.append(j+nums[i])
tmp[j+nums[i]]+=dp2[j]
if j-nums[i]>=0:
li.append(j-nums[i])
tmp[j-nums[i]]+=dp2[j]
for j in li:
dp[j]=i
dp2=tmp
print(dp2[nums[-1]])
수행시간: 72ms
Author And Source
이 문제에 관하여([백준-5557] 1학년), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sue06004/백준-5557-1학년저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)