수학과의 개발자 도전기

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

-정답풀이: 

-틀린 풀이: 

• while로 푸니까 무한루프 돌아서 시간초과 났음
• 새로운 nxn 행렬 만들어서 거기에 경로수 대입하는 걸로 생각하면 됨 
• 한번에 맞힐 수 있던 것 같아서 좀 아쉬운 문제 

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

문제를 이해하면 이전 타일문제와 점화식이 동일하다. 그렇게 풀어주면 끝. 풀이 도움없이 풀었던 문제 

-정답풀이:

• S(0)=1,S(1)=3,S(2)=7,S(3)=17,S(4)=41 
• 위 값들로 얻은 점화식은 다음과 같다
• S(i)=2*S(i-1)+S(i-2)

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

-정답 풀이: 

• 자료구조 설정

• 숫자들의 0번째 컬럼 값들이 불규칙적으로 입력돼서 어떻게 해야할지 잘 몰랐는데, sort()로 정렬하면됨(기억해두자)

• 결국 가장 긴 증가하는 부분수열 구하는 알고리즘이다. 이 수열에는 서로 교차하는 숫자가 존재 하지 않는다. 그 수가 최대이므로
• n에서 값을 빼면 최소로 교차하는 전깃줄 개수가 된다 

-전체풀이:

n=int(input())
dp=[0 for _ in range(n)]
w=[]
w_b=[]
for _ in range(n):
    w.append(list(map(int,input().split())))
    
#0번 컬럼에 숫자들 순서 맞춰서 정렬하기     
w.sort(key=lambda x:x[0])

#가장 긴 증가하는 부분수열 구하는 알고리즘     
for i in range(n):
    for j in range(i):
        if dp[i]<dp[j] and w[i][1]>w[j][1]:
            dp[i]=dp[j]
    dp[i]+=1
            
print(n-max(dp))
  
#가장 긴 증가하는 부분수열이면 교차할 수가 없음. 교차하는 거 최소니까 n에서 가장 긴수열 빼기

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

-정답풀이:

n,k=map(int,input().split())
dp=[[0]*201 for _ in range(201)]

for i in range(201):
    dp[1][i]=1
    dp[2][i]=i+1
    
for i in range(2,201):
    dp[i][1]=i
    for j in range(2,201):
        dp[i][j]=(dp[i][j-1]+dp[i-1][j])%10**9
print(dp[k][n])