[코독하구만 팀] 2021.01.27(수) - 6주차 개인 목표

- 목표 -

다이나믹 프로그래밍의 개념을 실습 문제를 통해 학습하고, 이를 응용하여 백준 문제에 적용해본다.

 

1. 피보나치

피보나치 수열의 N번째 항을 출력하시오.

 

[입력 값]

0

 

[출력 값]

0

 

[입력 값]

5

 

[출력 값]

5

 

[입력 값]

20

 

[출력 값]

6765

 

2. 가방

가방에 물건을 넣어 옮기려한다. 배낭에는 넣을 수 있는 물건 크기에 한계가 있으며, 각 물건은 크기와 가치가 부여되어있다.
배낭에 넣을 수 있는 물건들의 최대 가치를 구하시오.

 

[입력 값]

5 # 배낭 크기

4 # 물건 개수

2 3 4 5 # 물건 크기

3 4 5 6 # 물건 가치

 

[출력 값]

7

 

3. 제재소

재목을 만드는 제재소에는 재료로 들어온 나무를 정확히 K미터로 자르는 기계가 있다.
재료로 들어온 나무 관리를 위하여, 나무를 잘라 가능한 적은 갯수로 보관하려 한다.
예를 들어, 1 3 7미터로 자르는 기계가 있고 15미터 재료가 들어오면 7, 7, 1미터로 자르는 것이

가장 적은 나무 조각으로 자르는 방법이다.
나무 자르는 기계의 크기와, 재료 나무가 주어졌을 때 최소 나무 조각을 구하시오.

 

[입력 값]

3 # 자를 수 있는 크기의 개수

3 7 1 # 자를 수 있는 크기

15 # 주어진 나무의 크기

 

[출력 값]

3

 

4. 개구리 게임

개구리 게임은 화면 아래에서 화면 위로 발판을 밟아가며 올라가는 게임이다.
발판에 도착하면 각 발판에 배정되어있는 점수를 획득하며, 개구리는 왼쪽위, 위, 오른쪽위 발판으로 이동할 수 있다.
개구리 게임 발판 점수가 주어졌을 때, 개구리 게임에서 얻을 수 있는 최대 점수를 계산하시오.

 

[입력 값]

4 4 # 행, 열

1 2 5 0 # 점수 리스트

3 2 0 6

1 4 2 1

5 1 3 2

 

[출력 값]

16

 

5. 백준 1463번 - 1로 만들기

백준 1463번 - 1로 만들기 (www.acmicpc.net/problem/1463)

1463번: 1로 만들기