아주 상당히 헤매면서 풀었다. 실버 1이라 어려울 것이라 생각했는데 정답비율이 높았다. 난이도는 높지만 알고리즘만 이해하면 코드 구현을 쉬웠기 때문인거 같다.
우선 나는 노가다를 해가며 풀었다. k가 1일때부터 1,2,5가 가능한 조합을 전부 때려 넣어가며 숫자를 보았는데 규칙 일랑 하나도 보이지 않았다. 그래서 덩어리를 생각하며 풀어보기로 했다.
그래서 생각한 것이 이차원 배열로 나타내는 것이었다. 문제에서 주어진 예제가 아닌 다른 예제로 생각해 보겠다.
2 10
2
3
K | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
3 |
coin이 2인경우 k값에 따라 만들 수 있는 경우는 2로 나누어 떨어지는 경우이다. 이때는 2만 들어 가기 때문에 한가지 경우만 존재한다. 따라서 이것을 토대로 모든 배열을 채워준다.
그럼 3인 경우를 생각해보자. 이제 k는 2만이 아니라 3을 포함한 경우의 수를 만들 것이다.
그러면 경우의 수가 2개가 나온다.
1. 3을 포함하지 않고 K값을 만족하는 경우 -> 이전 dp[k] 값을 그대로 받는다.
2. 3을 포함하고 K값을 만족하는 경우 -> 3을 포함한다는 것은 K-3을 만족하는 값을 가져와야한다. -> dp[k-3]을 가져온다.
=> 결과적으로 점화식은 dp[k] = dp[k] + dp[k-3] 이 된다.
K | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
3 | 1 | 0 | 1 | 1 | 1 | 1 | 2 | 1 | 2 | 2 | 2 |
그러면 이 방식대로 코드를 짜주면 된다. 지금은 이차원 배열로 만들었지만 코드상에서는 일차원 배열로 만들어도 된다.
n,k = map(int, input().split())
coin = []
for _ in range(n):
coin.append(int(input()))
dp= [0 for i in range(k+1)]
dp[0] = 1
# 코인 초기화
for i in range(1, k+1):
if i % coin[0] == 0:
dp[i] += 1
# 코인 dp시작
for ci in range(1,n):
for i in range(1, k+1):
if i - coin[ci] >= 0:
dp[i] = dp[i] + dp[i-coin[ci]]
print(dp[-1])
다짜고 보니 다른 사람들 코드는 훨씬 간결하고 짧았다......먼가 불필요한 로직이 들어간거 같은데 일단 맞았으니.....ㅋㅋㅋㅋㅋ
다음에 다시 봐야겠다
'알고리즘' 카테고리의 다른 글
[python3] 백준 16236 풀이 ( 아기상어, 그래프, BFS, sort, pq? ) (0) | 2021.08.12 |
---|---|
[python3] 백준 1520 풀이 ( 내리막길, DP, DFS, 그래프 ) (0) | 2021.08.11 |
[python3] 백준 9465 풀이 ( 스티커, 다이나믹 프로그래밍, 이차원 배열 ) (0) | 2021.08.09 |
[c++] 백준 1629 풀이 ( 곱셈, 분할 정복을 이용한 거듭제곱, long long ) (0) | 2021.08.09 |
[python3] 백준 2252 풀이 ( 줄세우기, 위상정렬, DAG, 그래프 ) (0) | 2021.08.07 |