📌 다이나믹 프로그래밍 기초 문제 풀이 (이것이 취업을 위한 코딩 테스트다 with python)

📖 01. <문제> 개미 전사

✏️ 문제

🕶️ 해설

✍️ 입력

💻 출력
> 4
1 3 1 5

8

📖 02. <문제> 1로 만들기

✏️ 문제

🕶️ 해설

✍️ 입력

💻 출력
> 26
3

📖 03. <문제> 효율적인 화폐 구성

✏️ 문제

-> N*M = 1,000,000이므로 시간초과가 나지 않는다.

🕶️ 해설

-> 1원 짜리로 10000원까지 만들 수 있으니 무한대의 값을 10001로 설정하자.

✍️ 입력

-> 문제에서 식량창고 N이 최대 100개이기 때문에 DP테이블의 길이를 100으로 잡았다.

💻 출력
> 2 15

2
3

📖 04. <문제> 금광

✏️ 문제

🕶️ 해설

✍️ 입력

💻 출력
>2
3 4
1 3 3 2 2 1 4 1 0 6 1 2
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2

19
16

📖 05. <문제> 병사 배치하기

✏️ 문제

🕶️ 해설

✍️ 입력

💻 출력
>7
15 11 4 8 5 2 4

2

[출처] 이것이 취업을 위한 코딩테스트다 with python (나동빈 지음)