[파이썬] 백준 5557 : 1학년 (골드5)

[파이썬] 백준 5557 : 1학년 (골드5)

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

---

풀이

방향성 생각

• DFS + DP로 풀이
• 배열을 탐색하면서 cumsum이 0미만, 20초과가 되는 경우에서 가지치기를 해준다.
• 마지막 인덱스에 도달하면 등식 성립 확인해서 맞으면 1, 아니면 0.
• 이외의 경우에는 탐색 + 메모제이션.

 

---

전체코드

N = int(input())
arr = list(map(int,input().split()))

dp = {}

def dfs(idx,cumsum):

    # 탈출조건
    if cumsum < 0 or cumsum > 20:
        return 0

    # 종료조건
    if idx == N-1:
        return 1 if cumsum == arr[-1] else 0

    # 메모제이션
    if (idx,cumsum) in dp:
        return dp[(idx,cumsum)]

    # 탐색
    dp[(idx,cumsum)] = dfs(idx+1,cumsum+arr[idx]) + \
                        dfs(idx+1,cumsum-arr[idx])
    return dp[(idx,cumsum)]

print(dfs(1,arr[0]))

코멘트

• .