[백준알고리즘] 5557번: 1학년 -Python

[백준알고리즘] 5557번: 1학년 -Python

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

5557번: 1학년

별생각 없이 딕셔너리를 이용해서 풀었다. 현재까지의 누적 계산량과 인덱스를 쌍으로 하는 튜플을 키로 이후 가능한 경우의 수를 기록했다.

 

다 풀고나니 DP로 풀면 된다는 것을 깨달았다 ㅎㅎ;

딕셔너리와 재귀를 사용했는데 반복문으로도 충분히 풀 수 있었기 때문에 반복문과 리스트로 메모리를 잡아놓고 사용하는 방법을 사용하면 더 빠르게 통과할 것이다.

 

다음에 풀면 그렇게 풀겠지?

def solve(now, idx):
    if visited.get((now, idx)):     
        return visited[(now, idx)]

    visited[(now, idx)] = 0
    if idx == len(math):
        if now == res:
            visited[(now, idx)] = 1
        return visited[(now, idx)]
    
    if now + math[idx] <= 20:
        visited[(now, idx)] += solve(now+math[idx], idx+1)
    if 0 <= now - math[idx]:
        visited[(now, idx)] += solve(now-math[idx], idx+1)
    return visited[(now, idx)]

n = int(input())
math = list(map(int, input().split()))
math, res = math[:-1], math[-1]
visited = {}
solve(math[0], 1)
print(visited[(math[0], 1)])

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다