수학과의 개발자 도전기

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

-정답풀이: 

n,k=map(int,input().split())
c=[]
dp=[0 for i in range(k+1)]
for i in range(n):
    c.append(int(input()))
    
for i in range(1,k+1):
    a=[]
    for j in c:
        if j <=i and dp[i-j]!=-1:
            a.append(dp[i-j])
    if not a:
        dp[i]=-1
    else:
        dp[i]=min(a)+1
print(dp[k])

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

어떻게 푸는지 몰랐는데 찾아보니까 dfs(깊이 우선탐색)+dp를 이용해서 풀어야하는 문제. 

-원리(출처: https://chldkato.tistory.com/114)

• dfs + dp로 목적지까지 도착할 수 있는지 검사한다
• 루프를 방지하기 위해 방문 확인 배열 c를 -1로 초기화하고 이동할 때마다 0으로 다시 설정해준다

• 1. 과정을 진행하면서 c에 이미 저장된 값이 0이면 목적지까지 갈 수 없으므로 0을 반환한다
• 2. 1 이상의 값이면 이전에 그만큼 방문 경로가 있으므로 해당 값을 반환해서 더해준다
• 3. -1이면 방문하지 않은 경로이므로 dfs + dp 수행 

-정답풀이: 

m,n = map(int,input().split())
a=[]
for i in range(m):
    a.append(list(map(int,input().split())))

c=[[-1]*(n) for i in range(m)]   

dx=[1,-1,0,0]
dy=[0,0,1,-1]

def dfs(x,y):
    if x==m-1 and y ==n-1:
        return 1
    if c[x][y]!=-1:
        return c[x][y]
    c[x][y]=0
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<= nx < m and 0<=ny<n:
            if a[nx][ny]<a[x][y]:
                c[x][y]+=dfs(nx,ny)
    return c[x][y]

print(dfs(0,0))

-전체풀이: 

• 파이썬으로 실행하면 Recurssion Error 때문에 Pypy3로 실행해야한다
• 세로 리스트가 입력된다는 것을 알고 문제를 풀어야한다 

• 초기값 설정. m이 컬럼 개수, n이 행 개수. 컬럼위주로 진행해야한다(4,5번라인)
• 이해 안가는 부분: 7번(밑에처럼 하면 mxn 행렬이 만들어지는 것 아닌가?)

• dx=[동,서,북,남] ,  dy=[동,서,북,남] 을 표현 한 것 같음 

• 인덱스가 행렬 가장 오른쪽 아래면 멈추고 1 반환한다 

• 값이 -1이 아니면 이 전에 방문된 기록이 있으므로 그 기록을 반환한다

• 이제 c[x][y]==-1이면 방문하지 않은 경로이고, 루프를 막아야하므로 0으로 초기화하고 시작한다 
• nx의 값으로는 x-1,x,x+1이 가능하다. ny도 마찬가지 
• 해당 인덱스의 동서남북 값을 비교하는 과정 

• (x,y)의 상하좌우 값 중에 작은 값들이 있을 경우에만 dfs값 넣는다 

• 왼쪽 가장 위 값부터 시작해서 (0,0)으로 대입하는 건가? 

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

• 점화식을 구하기가 어려웠던 문제. 
• 일단 n이 홀수인 경우에 모두 답이 0이라 짝수를 중심으로 진행해야한다.
• 점화식: P(n)= 3*p(n-2)+2*p(n-4)+,,,,+2*p(0)

-정답풀이: 

-풀이 이해하는데 시간이 좀 걸렸다

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

콤비네이션만 알면 풀 수 있었던 문제

-정답풀이: 

• 4번에서 나눌때 '/'가 아닌 '//'로 해야한다
• 마지막에 답 출력할 때 10007로 나누기!!(매번 빼먹고 틀린다)

import math
n,k=map(int,input().split())

answer=math.factorial(n)//(math.factorial(k)*math.factorial(n-k))
print(answer%10007)