[백준 5557번] 파이썬 - 1학년

백준 5557_1학년

# Problem

• 줄 지어있는 숫자 들이 있을 때 아래의 조건을 지키며 등식을 완성하여라
  • 마지막 두 숫자 사이에는 '=', 나머지 숫자 사이에는 '+'또는 '-'
  • 이 때, 왼쪽부터 계산을 할 때, 중간 결과값이 모두 0이상 20이하여야 한다.
• 올바른 등식의 수를 구하는 프로그램 작성

# 접근 방법

• 모든 경우의 수를 구하게 되면 2^100의 경우의 수가 생기므로 dp로 풀어야 될 것 같다.
• bottom-up 방식으로 DP TABLE 이용
• DP TABLE의 경우 최댓값이 20이 넘어가면 안된다는 조건이 있기 때문에 21개만 만들어주면 된다.
• 점화식

equation[i][j+number[i]] += equation[i-1][j]  
equation[i][j-number[i]] += equation[i-1][j]

import sys  
input = sys.stdin.readline  

N = int(input())  
number = list(map(int, input().split()))  
result = number.pop()  
# dp table 생성  
equation = [[0] * 21 for _ in range(N-1)]  
# 주어진 수식의 처음 값을 기록해준다.  
equation[0][number[0]] = 1  

# 수식 돌면서  
# N-2만큼만 해주면 된다  
# 예시1의 경우 11개의 수 받아서 마지막 숫자 POP 해서 N =  10개이므로  
# 인덱스는 9가 최대  
for i in range(1, N-1):  
    # dp table에 기록  
    for j in range(21):  
        # 직전까지의 등식의 결과값이 있는 곳을 찾아준다.  
        # i는 등식의 순서        
        # j는 등식 결과값 = 인덱스        
        if equation[i-1][j]:  
            # 지금 계산할 결과값이 조건범위 내에 있다면  
            if j+number[i] <= 20:  
                # 경우의 수를 더해준다  
                equation[i][j+number[i]] += equation[i-1][j]  
            if j-number[i] >= 0:  
                equation[i][j-number[i]] += equation[i-1][j]  

# 인덱스 마지막 번호 = N-2 --> 10번째 등식 = 9번의 인덱스  
print(equation[N-2][result])

• DP의 경우 점화식 만들어 주는 것이 중요!!
• 또는 1차원 리스트로 dp를 만들어주고 각 인덱스의 숫자를 연산할 때 temp라는 새로운 1차원 리스트를 활용할수도 있다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N = int(input())  
nums = [*map(int, input().split())]  
dp = [0] * 21  
dp[nums[0]] = 1  
result = 0  
for i in range(1, N-1):  
    temp = [0] * 21  
    for j in range(21):  
        if dp[j]:  
            plus = j + nums[i]  
            minus = j - nums[i]  
            if plus <= 20:  
                temp[plus] += dp[j]  
            if minus >= 0:  
                temp[minus] += dp[j]  
            dp[j] = 0  
    dp = temp  
print(dp[nums[-1]])