수학과의 개발자 도전기

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

-정답풀이

i개의 카드를 구매하는 방법은 (이전에 i-j개 산 것 더하기 j개가 담긴 카드팩을 사는 방법)과 그냥 i개 사는 것이 있고

이 중에 최댓값을 구하면 된다 

n=int(input())
dp=[0]*(n+1)
data=[0]+list(map(int,input().split()))
dp[1]=data[1]
for i in range(2,n+1):
    for j in range(1,i+1):
        dp[i]=max(dp[i],dp[i-j]+data[j])
print(dp[n])

-틀린풀이

처음에는 주어진 n의 약수들로만 계산헀을 때, 최댓값을 구할 수 있다고 생각했는데

마지막 예제에서 내가 생각한 방법으로는 16이 나오는데, 답은 18이다. 

이걸보고 약수로만 하는 것이 아니고, 더하기를 통해서 최댓값을 구해야한다고 생각했다. 

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

answer=0
for i in range(1,n+1):
    if n%i ==0:
        answer=max(answer,data[i]*(n//i))
print(answer)

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

-정답풀이:

서쪽에서 n개 만큼을 선택한 후 순서대로(겹치지 않게) 동쪽과 연결해주면 된다. 따라서 조합을 이용하면 된다 

주의할 점

나눌 때 '/'로 하면 몫이 답.0으로 소수로 출력되고, '//'로 하면 답은 정수로 출력된다. 

from itertools import combinations는 특정 리스트에서 n개를 조합할 때 사용하고, 

특정 조합의 수를 구하려면 math의 factorial와 조합의 공식(n!/(n-r)!r!)을 이용해서 답을 구해야한다 

import math
t=int(input())

for _ in range(t):
    n,m=map(int,input().split())
    answer= math.factorial(m)//(math.factorial(m-n)* math.factorial(n))
    print(answer)

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

풀이 보면서 정수 삼각형이랑 비슷하다고 느낀 문제. 

처음에는 점화식이 dp[i]=dp[i-1]*2-1이라고 생각했는데 바로 틀렸다. 

이는 숫자에서 +-1을 하는데, 0은 -1이 안되므로 1밖에 없고, 9도 +1하면 10이라서 안되니까 8밖에 없어서 

0과 9일 때 제외는 모든 이전 자리수에서 가져오면 된다. 

-정답 풀이

n=int(input())
dp=[[0 for _ in range(10)] for _ in range(101)] 
for i in range(1,10):
    dp[1][i]=1
for i in range(2,n+1):#2부터 n자리 수까지
    for j in range(10): #0부터 9에 대해서 진행
        if j==0:
            dp[i][j]=dp[i-1][1]
        elif j==9:
            dp[i][j]=dp[i-1][8]
        else:
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]
print(sum(dp[n])%(10**9))

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

이전에 풀었던 계단 올라가기와 동일한 문제인데 다른점은 꼭 마지막 와인을 마시지 않아도 된다는 것. 

그래서 점화식에 추가할 것이 있다. 현재 와인을 마시지 않았을 조건(dp[i-1])

이에 대한 자세한 설명은 여기서 볼 수 있다.

https://www.acmicpc.net/board/view/60664

dp[i]=max(dp[i-3]+data[i-1]+data[i],dp[i-2]+data[i],dp[i-1])

이 외에는 계단 올라가기와 동일하다. 

그동안 IndexError가 발생했던 이유가, n에 따라 data와 dp 리스트를 생성하면

n==1, n==2일 때는 숫자가 모자라서 for문을 못 돌린다. 그래서 조건에 따라 if, elif문을 작성하면 된다 

n=int(input())
data=[]
for _ in range(n):
    data.append(int(input()))
if n==1:
    print(data[0])
elif n==2:
    print(data[0]+data[1])
else:    
    dp=[0]*n
    dp[0]=data[0]
    dp[1]=data[1]+data[0]
    dp[2]=max(data[2]+data[0],data[2]+data[1],dp[1]) #dp[2]=dp[1]은 2번째 와인을 마시지 않았다는 말
    for i in range(3,n):
        dp[i]=max(dp[i-3]+data[i-1]+data[i],dp[i-2]+data[i],dp[i-1])
    
    print(max(dp))