수학과의 개발자 도전기

-문제: https://www.acmicpc.net/problem/11722

이거는 가장 긴 증가하는 수열을 n-1 부터 진행하면 된다 

풀이는 거의 똑같지만, 반복문 범위가 n-1부터 시작해 -1씩 진행하면 된다 

-정답풀이:

n=int(input())
data=list(map(int,input().split()))
dp=[0]*n
for i in range(n-1,-1,-1):#n-1에서 0까지 -1씩 진행
    for j in range(n-1,i-1,-1): #n-1부터 i까지 -1씩 진행
        if data[i]>data[j] and dp[i]<dp[j]:
            dp[i]=dp[j]
    dp[i]+=1
print(max(dp))

-문제: https://www.acmicpc.net/problem/11055

이전에 풀었던 가장 긴 증가하는 부분 수열의 변형 문제다. 

처음에는 그대로 풀었다가 긴 수열을 구성하는 숫자의 합이라는 것을 알고 

+=1 대신 +=data[i]을 했더니 정답이 떴다 

-정답풀이 

n=int(input())
data=list(map(int,input().split()))
dp=[0]*n

for i in range(n):
    for j in range(i+1):
        if data[i]>data[j] and dp[i]<dp[j]:
            dp[i]=dp[j]            
    dp[i]+=data[i]
    
print(max(dp))

-문제: https://www.acmicpc.net/problem/12865

-정답풀이: 

풀이 방법 익혀야겠다

dp의 열이 k까지 있으므로 j가 반복문을 돌면서, 가방의 크기가 점점 커지고 있고, 거기에 물건을 넣는 거라고 생각하면 될 것 같다 

if j < weight[i] (가방이 현재 담을 수 있는 무게(j)가 물건의 무게보다 적은경우)

위 상황에서는 물건을 가방에 넣을 수 있는 상황이 아니므로 이전 물건의 같은 무게 값을 누적한다 

if j >= weight[i] (가방이 현재 담을 수 있는 무게가 물건의 무게보다 큰 경우)

이 상황에서는 현재 물건을 담을 수 있다. 근데 가치를 최대로 해야하기 때문에 

max(이전물건, 같은무게 / 이전물건+(현재 물건 넣기 전 무게)의 가치에 현재 물건의 가치)를 계산한다 

n,k=map(int,input().split())
weight=[0]
value=[0]
for _ in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
    
dp=[[0]*(k+1) for _ in range(n+1)]

for i in range(1,n+1): #i가 현재 물건
    for j in range(1,k+1): #j가 현재의 무게
        if j >= weight[i]:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][k])

-문제:https://www.acmicpc.net/problem/2293

대충 문제 과정 2 x k 행렬은 생각했는데, 이걸 어떻게 코드로 옮겨야할지 몰랐다 

 문제의 목적이 주어진 동전들로 k원을 만드는 가짓수를 구하는 것이다. 

j원이 해당 단계의 동전(i원)보다 크다면 i원과 j-i원으로 j원을 만들어야 한다. 

j-i원을 만드는 가짓수에 i만 추가하면 되므로 이는 변하지 않는다. 

그리고 두번째 dp[j]는 i번째 동전 이전 동전들로 j원을 만들었던 가짓수 이다. 

누적된 j원 만드는 가짓수에 i로 만들 수 있는 경우를 세면된다 

그래서 dp[j]=dp[j]+dp[j-i] 

-정답풀이:

n,k=map(int,input().split())
coins=[]
for _ in range(n):
    coins.append(int(input()))
dp=[0]*(k+1)
dp[0]=1
for i in coins:
    for j in range(1,k+1):
        if j>=i:
            dp[j]+=dp[j-i]
print(dp[k])