이.코.테 1로 만들기, 개미 전사(python3)

p. 217

1로 만들기 코드

data = [0] * 30001
# data[1] = 0
# data[2] = 1
# data[3] = 1
# data[4] = 2
# data[5] = 1

X = int(input())

# for i in range(6, X + 1):
#     ans1 = 9999999
#     ans2 = 9999999
#     ans3 = 9999999
#     ans4 = 9999999
#     if i % 5 == 0:
#         ans1 = data[i // 5] + 1
#     if i % 3 == 0:
#         ans2 = data[i // 3] + 1
#     if i % 2 == 0:
#         ans3 = data[i // 2] + 1
#     ans4 = data[i - 1] + 1
#     data[i] = min(ans1, ans2, ans3, ans4)
#
# print(data[X])

for i in range(2, X + 1):
    data[i] = data[i - 1] + 1
    if i % 2 == 0:
        data[i] = min(data[i], (data[i // 2] + 1))
    if i % 3 == 0:
        data[i] = min(data[i], (data[i // 3] + 1))
    if i % 5 == 0:
        data[i] = min(data[i], (data[i // 5] + 1))

print(data[X])

 

주석 처리된 부분은 내가 작성한 코드다.

책의 정답 코드가 더 깔끔해서 다시 작성해 보았다.

간단히 숫자 2부터 차례대로 정답까지 최솟값을 갱신해 나가면 된다.

 

p. 221

개미 전사 코드

data = [0] * 101
N = int(input())
eat = list(map(int, input().split()))

data[0] = eat[0]
data[1] = max(eat[0], eat[1])
#data[2] = max(eat[1], eat[0] + eat[2])
for i in range(2, N):
    #data[i] = data[i - 3] + eat[i]
    data[i] = max(data[i], data[i - 1])
    data[i] = max(data[i], data[i - 2] + eat[i])
print(data[N - 1])


# #책 정답임.
# # 정수 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])
# for i in range(2, n):
#     d[i] = max(d[i - 1], d[i - 2] + array[i])
#
# # 계산된 결과 출력
# print(d[n - 1])

내가 작성한 코드는 i-3까지 고려해서 작성했지만 알고보니 i - 3까지는 고려하지 않아도 됐다. 이미 계산이 완료되어있기 때문이다. 그래서 i-3을 고려하는 코드를 제거해도 답은 제대로 잘 나왔다.