19. 다이나믹 프로그래밍 : 타일 깔기, 효율적인 화폐 구성

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다.

1 * 2, 2 * 1, 2 * 2의 덮개로 채울 때 모든 경우의 수를 구하라.

N이 3인, 즉 2 * 3 크기의 바닥을 채우는 경우의 수는 5가지이다.

 

input : 

3

output :

5

N = int(input())

memory = [0]* 1000

memory[0] = 1

memory[1] = 3

for i in range(2, N):
  memory[i] = memory[i-1] +memory[i-2] * 2
  
print(memory[i])

이 문제는 그림을 그려가며 규칙을 찾아서 풀었다.. 후 그림 그리고 규칙을 찾는 것이 중요할 듯..

 

효율적인 화폐 구성

 

N가지 종류의 화폐가 있다. 이 화폐들의 구성을 최소한을 이용하여 가치의 합이 M원이 되게 하라.

N, M = map(int,input().split())

unit = []

memory = [10001] * 10001

for i in range(N):
  unit.append(int(input()))

memory[0] = 0


for i in range(N):
  for j in range(M+1):
    memory[j] = min(memory[j], memory[j - unit[i]]+1)

print(memory[M])

점점 이해가 가기 시작한다.!!! 알고리즘 마스터 가즈아~~