221117 정리

1. DP

   특정한 문제를 완전탐색으로 수행했을 때, 시간이 매우 오래걸린다면 다니아믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해본다.

   가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것이 권장됨.

예시) 피보나치 구현
1. 탑 다운 방식(재귀함수 이용)

d = [0]*100

def fibo(x):
	if x==1 or x==2:
    	return 1
    if d[x]!=0:
		return d[x]
    d[x] = fibo(x-1)+fibo(x-2)
    return d[x]

2. 바텀업 방식(반복문 사용)

d[0]*100
d[1] = 1
d[2] =1
n=99

for i in range(3,n+1):
	d[i]= d[i-1]+d[i-2]

print(d[n])

1) 1로 만들기

정수 X가 주어질 때 정수 X에서 사용할 수 있는 연산 4가지가 있음.
1. X가 5로 나누어떨어지면, 5로 나눈다.
2. X가 3으로 나누어떨어지면, 3으로 나눈다.
3. X가 2로 나누어떨어지면 2로 나눈다.
4. X에서 1을 뺀다.
이 연산을 적절히 이용해서 1을 만들려고 한다.
연산을 사용하는 최소 횟수를 구하라

x = int(input())
d=[0]*30001
d[0] = 0
d[1] = 0
for i in range(2,X+1):
	d[i] = d[i-1]+1
    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)
print(d[X])

2) 개미 전사

개미 전사가 메뚜기 마을의 식량창고를 공격하려고 한다. 여러 개의 식량창고가 있는데, 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며, 개미 전사는 식량창고를 선택적으로 약탈한다. 이 때, 일직선상에 존재하는 식량창고 중 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.
이 때, 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때, 얻을 수 있는 식량의 최댓값을 구하여라.

N = int(input()) #3<=N<=100
arr = list(map(int,input().split()))
# 0<=arr[i]<=1000
d = [0]*100
d[0] = arr[0]
d[1] = max(arr[0],arr[1])
for i in range(2,N):
	d[i] = max(d[i-1],d[i-2]+arr[i])
print(d[N-1])

고려할 점

1) i-1 번째 창고가 털렸으면 i번째 창고는 털 수 없음
2) i-2 번째 창고가 털렸으면 i번째 창고는 털 수 있음.
이 두 경우 중, 더 큰 값을 구하면 됨. 그래서

d[i] = max(d[i-1],d[i-2]+k) 

점화식 완성됨. (k는 i번째 창고에 들어있는 식량의 무게)

3) 바닥 공사

가로 길이가 N, 세로 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1X2, 2X1,2X2 덮개를 이용해 채우려고 한다.
이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2X3을 채우는 경우의 수는 5이다.

출력조건) 첫째 줄에 2XN 크기의 바닥을 채우는 방법의 수를 796,796 으로 나눈 나머지를 출력하라

N = int(input()) #1<=N<=1,000
d=[0]*1001
d[1] =1
d[2] = 3
for i in range(3,N+1):
	d[i] = (d[i-1]+d[i-2]*2)%796796
print(d[N])

경우의 수
1) i-1까지 타일이 채워져있다면, 가로길이가 1인 타일은 하나뿐이므로 d[i] = d[i-1]
2) i-2까지 타일이 채워져있다면, 가로길이가 2인 타일은 2가지 이므로 d[i] = d[i-2]X2
따라서 모든 경우의 수를 구하는 것이므로
d[i] = d[i-1]+d[i-2]X2

4) 효율적인 화폐 구성

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이 때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원,3원 단위의 화폐가 있을 때 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.
1<=N<=100 , 1<=M<=10000
화폐 가치<=10000
불가능할 때는 -1을 출력한다.

N,M = map(int,input().split())
arr=[]
for i in range(M):
	arr.append(int(input())
d=[10001]*(M+1)
d[0] = 0
for i in range(N):
	for j in range(arr[i],M+1):
    	if d[j-arr[i]]!=10001:
        	d[j] = min(d[j-arr[i]],d[j])
if d[M]==10001:
	print(-1)
else:
	print(d[M])