https://www.acmicpc.net/problem/5557
[초기 접근 방법(o)]
1. 먼저 dp 메모제이션 할 배열을 정의하자
2. dp[i][j] : i번째 수까지 보았을 때, 수식을 만들어서 j가 나오는 경우의 수
- 0 <= i <= N-1, 모든 수를 끝까지 보자. (결국 0이 나오면 등식이 성립한 꼴)
- 0 <= j <= 20, 나오는 수는 0이상 20이하이어야 한다.
3. 점화식
dp[i][j] += dp[i-1][j-lst[i]]
dp[i][j] += dp[i-1][j+lst[i]]
이전 i-1번째까지 보았을 때, 현재 j +- lst[i] 하여 i번째에서 j가 나오는 수를 구한다.
[생각]
'초기 접근 방법'으로 풀었는데 틀렸다.
음.. dp 배열의 정의와 점화식은 맞았으나, 모든 수를 끝까지 본 게 원인이었다.
0 0 0 인 경우문제에서 원하는 답은 2개이다. (0+0=0, 0-0=0)하지만 위의 접근대로 풀 경우 4개가 나온다., (0+0+0, 0+0-0, 0-0+0, 0-0-0)
[코드]
# 풀이 시간 : 40분
# 시간복잡도 : O(21N)
# 공간복잡도 : O(21N)
# 참고 : -
N = int(input())
lst = list(map(int, input().split()))
# dp[i][j] : i번째 수까지 보았을 때, 수식을 만들어서 j가 나오는 경우의 수
# 0 <= i <= N-1 // 모든 수를 끝까지 보자. (결국 0이 나오면 등식이 성립한 꼴)
# 0 <= j <= 20 // 나오는 수는 0이상 20이하이어야 한다.
# 모든 수를 끝까지 본 게 패착
# 0 0 0 인 경우 : (+, +) (+, -) (-, +) (-, -) 4개가 나온다.
dp = [[0] * 21 for _ in range(N)]
# 초기 dp 설정
# 0번째 수까지 보았을 때, 0번째 수가 나오는 경우는 본인 자신 1개이다.
dp[0][lst[0]] = 1
for i in range(1, N-1): # 마지막 수 제외
for j in range(21):
# 이전 dp값에서 현재 lst값을 +- 하여 범위에 맞을 경우
# 경우의 수를 카운트 해주면 된다.
if 0 <= j - lst[i] <= 20:
dp[i][j] += dp[i-1][j-lst[i]]
if 0 <= j + lst[i] <= 20:
dp[i][j] += dp[i-1][j+lst[i]]
# 마지막 수를 제외한 idx까지 보았을 때, 수식을 만들어서 lst[-1]이 나오는 경우의 수를 출력하면 된다.
print(dp[N-2][lst[-1]])
'Algorithm > DP' 카테고리의 다른 글
[백준] 7579번 앱 _ Python (0) | 2024.02.23 |
---|---|
[백준] 14925번 목장 건설하기 _ Python (1) | 2024.01.30 |
[백준] 2228번 구간 나누기 _ Python (0) | 2023.11.24 |
[백준] 17626번 Four Squares _ Python (0) | 2023.11.23 |
[백준] 17626번 Four Squares _ Python (0) | 2023.11.17 |