수학과의 개발자 도전기

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

문제에 점화식을 유추할 수 있는 정보가 있어서 그걸 토대로 점화식을 작성한 후 코드를 작성하니 정답이 떴다

점화식: p(n)=p(n-3)+p(n-2)

-정답풀이:

각 테스트마다 쓰이는 dp는 달라야하므로 dp 초기화하는 것은 for문 안에다가 넣어준다 

t=int(input())

for _ in range(t):
    dp=[1,1,1]
    n=int(input())
    for i in range(3,n):
        dp.append(dp[i-3]+dp[i-2])
    print(dp[n-1])

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

-정답풀이

길이 별로 갯수를 구해보면 피보나치 수열을 이룬다

정답 출력할 때 15746으로 나누는 거 잊지말기!! 

값 삽입할 때 나눈 값을 넣어야 메모리 초과가 발생하지 않는다 

n=int(input())
dp=[1,2]

for i in range(2,n):
    dp.append((dp[i-1]+dp[i-2])%15746)
    
print(dp[n-1])

-문제: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)