[백준][DP] 5557. 1학년

1학년

5557번: 1학년

 

• 첫 풀이 - fail
  • ⚠️시간초과
  • dfs 로 +,- 돌면 2^n (3 ≤ N ≤ 100) 로 당연히 시간초과 나는데 안보고 dfs로 풀어버림 --...
  • → 풀다가 dp인거 깨달음

n = int(input())
number = list(map(int, input().split()))
m = len(number)
answer = 0


def dfs(tmp, cnt):
    global answer
    if eval(tmp) < 0 or eval(tmp) > 20:
        return
    if cnt == m-1:
        if eval(tmp) == number[-1]:
            answer += 1
        return

    dfs(tmp+"+"+str(number[cnt]), cnt+1)
    dfs(tmp+"-"+str(number[cnt]), cnt+1)


dfs(str(number[0]), 1)

print(answer)

 

 

• 두번째 풀이 -fail
  • 시간초과안나려면 앞에했던 것들을 기억해야함 → DP
  • ⚠️메모리 초과

n = int(input())
number = [0]+list(map(int, input().split()))

dp = [[] for _ in range(n)]
dp[0].append(0)
for i in range(1, n):
    for j in dp[i-1]:
        if j+number[i] <= 20:
            dp[i].append(j+number[i])
        if j-number[i] >= 0:
            dp[i].append(j-number[i])

print(dp[n-1].count(number[-1]))

 

• 세번째 풀이 - fail
  • ⚠️메모리 초과
  • 비우고 다시 채우는 식으로 했는데도 메모리초과
  • 일단 담는 과정에서ㅜ 초과나는것 같음

n = int(input())
number = [0]+list(map(int, input().split()))

dp = [[] for _ in range(2)]
dp[0].append(0)
for i in range(1, n):
    for j in dp[0]:
        if j+number[i] <= 20:
            dp[1].append(j+number[i])
        if j-number[i] >= 0:
            dp[1].append(j-number[i])

    dp[0] = dp[1][:]
    dp[1].clear()

print(dp[0].count(number[-1]))

 

• 다른 사람 풀이
  • 구해진 값을 저장하는게 아니라 
  • 구해진 값의 위치에 가능한 횟수를 +1 씩 해주는 것

n=int(input())
dp=[[0 for _ in range(21)] for _ in range(n)]
number=list(map(int, input().split()))

# 처음 숫자 셋팅
dp[0][number[0]]=1

for i in range(1, n-1):
    for j in range(21):
    # 지난 계산했던 기록이 있는 행일 경우만 계산한다.
        if dp[i-1][j]:
            # 덧셈일 경우
            if 0<=j+number[i]<=20:
                dp[i][j+number[i]] += dp[i-1][j]
                
            # 뺄셈일 경우
            if 0<=j-number[i]<=20:
                dp[i][j-number[i]] += dp[i-1][j]

# 입력받았던 숫자 중 마지막 숫자와 일치하는 경우의 수가 얼마인지 출력
print(dp[n-2][number[-1]])