|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
# 정수 X를 입력받기
x = int(input())
# 앞서 계산된 결과를 저장하기 위한 dp 테이블 초기화
d = [0] * 30001
# 다이나믹 프로그래밍(Dynamic programming) 진행(보텀업)
for i in range(2, x+1):
# 현재의 수에서 1을 빼는 경우
d[i] = d[i - 1] +1
# 현재의 수가 2로 나누어 떨어지는 경우
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] +1)
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] +1)
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] +1)
|
cs |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
# 정수 N를 입력받기
n = int(input())
# 모든 식량 정보 입력받기
array = list(map(int, input().split()))
# 앞서 게산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1])
print(d[1])
for i in range(2, n):
d[i] = max(d[i-1], d[i-2]+array[i])
#게산된 결과 출력
print(d[n - 1])
|
cs |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
# 정수 N을 입력 받기
n = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1001
# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[1] = 1
d[2] = 3
for i in range(3, n + 1):
d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796
# 계산된 결과 출력
print(d[n])
|
cs |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
# 효율적인 화폐 구성
# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
array.append(int(input()))
# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)
# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
for j in range(array[i], m+1):
if d[j - array[i]] != 10001: # (i-k)원을 만드는 방법이 존재하는 경우
d[j] = min[d[j],d[j - array[i]]+1]
# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
print(-1)
else:
print(d[m])
|
cs |
'알고리즘 문제 > 자료구조&알고리즘' 카테고리의 다른 글
| 최단경로 예제 (0) | 2020.10.24 |
|---|---|
| 최단 경로 (0) | 2020.10.23 |
| 다이나믹 프로그래밍 (0) | 2020.10.22 |
| 다이나믹 프로그래밍 (0) | 2020.10.22 |
| 이진 탐색 예제 (0) | 2020.10.22 |