[DP] 4문제
출처 - 이것이 코딩테스트다 with Python
1. 1로 만들기
코드
N = int(input())
count=0
d=[0]*(N+1)
#dp[1]=0
for i in range(2,N+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[N])
숫자i는 i-1에 1을 더한것이므로, d[i] = d[i-1]+1을 해준다. (1을 빼주는 방법 d)
그 후 숫자 i가 2,3,5의 배수인지를 확인하여 최소 연산을 하는 경우의 수를 저장하도록 한다.
2. 개미전사
코드
n = int(input())
stock = list(map(int,input().split()))
dp=[0]*(n+1)
dp[0]=stock[0]
dp[1]=max(stock[0],stock[1])
for i in range(2,n):
dp[i]=max(dp[i-1],dp[i-2]+stock[i])
print(dp[n-1])
i번째에서 선택할 수 있는 최댓값을 구하는 방식으로 했다(bottom-up방식)
3. 바닥 공사
코드
n = int(input())
dp=[0]*(n+1)
dp[1]=1
dp[2]=3
for i in range(3,n+1):
dp[i] = (dp[i-1]+(2*dp[i-2]))%796796
print(dp[n])
i-1번째의 값에 1X2짜리를 붙이는 방법과 i-2번째에 2X1 2개를 붙이거나 2X2짜리 1개를 붙이는 방법이 있다.
이를 점화식으로 표현하면 dp[i] = dp[i-1]+ 2*dp[i-2]가 된다.
이 때, 매 값을 796796으로 나눈 나머지로 저장하라고 했기 때문에 나머지 연산을 해주었다.
4. 효율적인 화폐구성
코드
n,m = map(int,input().split())
coin=[]
for i in range(n):
tmp = int(input())
coin.append(tmp)
dp=[10001]*(m+1)
dp[0]=0
for i in range(n):
for j in range(coin[i],m+1):
if dp[j-coin[i]]!=10001:
dp[j] = min(dp[j],dp[j-coin[i]]+1)
if dp[m]==10001:
print(-1)
exit()
print(dp[m])
그리디로 풀던 방식에서 화폐의 단위가 바뀌면 푸는 방식이다.
Author And Source
이 문제에 관하여([DP] 4문제), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@isg/DP-4문제저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)