[boj] 5557_1학년_python

문제링크

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

5557번: 1학년

---

문제설명

 

문제

배열에 입력된 수 앞에 +나 -를 붙여나온 결과값이 배열에 처음 입력된 수와 일치하는 경우의 수를 구해야 한다.

배열의 연산 과정에서 음수나 20이 넘는 수는 나올 수 없다.

 

입력

1.  숫자의 개수 N

2.  0 이상 9 이하의 정수 N개

 

출력

1. 상근이가 만들 수 있는 올바른 등식의 개수

 

제한

• 3 ≤ N ≤ 100
• 출력 :  2^63 -1 

---

문제풀이

처음 DP 배열을 확인해보면

DP[ ( 0 ~ 20)의 범위를 가지는 경우의 수 ][ 입력된 수의 개수]

정도로 이해할 수 있다.

 

우리가 이 문제를 푸는데 쓰는 내용만을 다시 써보면

DP[ j ± lst[ i ] ] [ i ] = DP[ j ][ i -1 ]인데

j는 이전 연산, i - 1은 이전 연산까지 쓰인 ± 연산자 수 or 이전까지 완료된 연산의 수

lst[ i ]는 더해지거나 빼진 수, i 는 이전 연산까지 쓰인 ± 연산자의 수라고 이해할 수 있다.

 

다시 말하면 

DP[ +, -연산자의 개수만큼의 연산의 결과 즉 배열의 덧셈 결과(0~20) ][ 현재 진행된 연산의 수 ]

라고 이해할 수 있다.

다음 내용을 확인한 채로 코드를 확인해보자.

---

초기 접근

재귀를 이용해서 풀었더니 시간 초과가 났다.

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
N = int(input()) # 문자열 길이
DP = list(map(int, input().split())) # DP 배열
rangeLst = [0 for _ in range(21)]
ans = DP[0] # 올바른 등식의 결과
buf = 0
def gradeOne(num, idx):
    if idx == N:
        if 0<= num <= 20:
            rangeLst[num] += 1
        return
    if 0 <= num + DP[idx] <= 20:
        gradeOne(num + DP[idx], idx+1)
    if 0 <= num - DP[idx] <= 20:
        gradeOne(num - DP[idx], idx+1)

gradeOne(ans, 1)
print(rangeLst[ans])

 

그래서 메모이제이션을 이용해 다음과 같이 다시 풀어주었다.

# 시간 복잡도 : O(N*M) # M은 들어올 수 있는 숫자의 범위
# 공간 복잡도 : O(N*M) # M은 들어올 수 있는 숫자의 범위
# 풀이 시간 : 6시간
import sys
input = sys.stdin.readline
N = int(input()) # 문자열 길이
lst = list(map(int, input().split())) # 초기 리스트
DP = [[0 for _ in range(N)] for _ in range(21)]  # DP 배열
# 0부터 시작하므로 결과값에서는 -1을 해주어야 한다.
DP[lst[0]][0] = 1 # DP의 초깃값 : lst에 0번째 인덱스 결과는 1개

# 0~ N-1의 범위안에는 N개의 수가 입력되어있음.
# 0부터 입력되었기에 첫 번째 인덱스가 N-1인 경우가
# 일반적인 명칭에서 N번째의 수를 출력해줌
for i in range(1, N-1): # 0 ~ N-2번째까지의 인덱스를 참조하기 위해 이렇게 표현
    for j in range(21): # 0 ~ 20의 범위를 지키기 위해
        # 2차원 배열에서의 메모이제이션 활용
        # DP[( (+, - 연산자의 개수)번째까지의 덧셈 결과  )][ (+, -연산자의 개수)]
        # DP[( (+, - 연산자의 개수)번째까지의 덧셈 결과  )][ (+, -연산자의 개수)]

        # 결과에 양수를 더하는 경우
        if 0 <= j + lst[i] <= 20:
            DP[j + lst[i]][i] += DP[j][i -1]
        # 결과에 음수를 더하는 경우의 수
        if 0 <= j - lst[i] <= 20:
            DP[j - lst[i]][i] += DP[j][i - 1]

# N-2인 이유?
# 11개의 수 8 3 2 4 8 7 2 4 0 8 8에서
# 8+3+2-4-8-7+2+4+0+8=8 연산을 한다고 했을 때
# 현재 이 안에 들어있는 (+, - 연산자 개수)의 합은 10개이다.
# 즉 N(숫자의 수 : 11, 10번째 인덱스)개에서 그 안에 들어있는 연산자의 수는 10개, N-2개이기 때문에
# 2번째 인수가 N-2인 경우의 수가 올바른 등식의 개수를 반환한다.
print(DP[lst[N-1]][N-2])

 

---

참고 레퍼런스

1. https://boomrabbit.tistory.com/92

[ boj : 5557 ] 1학년