BOJ(1학년) 5557

작성일 | In

5557 1학년

  • 마지막 두 숫자 사이에 ‘=’를 넣고
  • 나머지 숫자 사이에는 ‘+’또는 ‘-‘를 넣어 등식을 만든다
  • +,- 넣는 경우 ->(마지막에는 ‘=’를 넣기 때문에) N-1개의 수 사이에 +와 -를 넣으므로
  • N-2가지가 정확한 표현.

  • 시간복잡도는 2^N이다

  • 문제의 주인공은 0부터 20까지만 안다.

  • 제약이 걸려있다.

  • 앞의 기타리스트에서는 합을 구한게 아닌 가장 큰 것을 구하는 문제.

  • 결국은 똑같은 점화식과 다이나믹 문제.

  • D[i][j] = i까지 수를 사용해서 j를 만드는 방법의 수

  • A[1] +- …+ A[i]= j

  • A[1] +- … - A[i]

  • i-1까지, j-A[i]를 만든 것

  • D[i]j-A[i]]

  • i-1까지 - A[i]

  • D[i]j+A[i]]

  • D[i][j] = D[i-1]j-A[i]] + D[i-1]j+A[i]]
n = int(input())-1
a = list(map(int,input().split()))
goal = a[-1]
a = a[:-1]
d = [[0]*21 for _ in range(n)]
d[0][a[0]] = 1
for i in range(1,n):
    for j in range(21):
        if j-a[i] >= 0:
            d[i][j] += d[i-1][j-a[i]]
        if j+a[i] <= 20:
            d[i][j] += d[i-1][j+a[i]]
print(d[n-1][goal])

참고자료 codeplus

0%