수학과의 개발자 도전기

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

이전에 풀었던 내리막길과 비슷한 문제라고 생각해서 dfs로 풀려고 했는데, 이중 for문으로 풀면 됐던 문제다. 

점프를하기때문에 연속적으로 움직이지는 않는다고 생각해 for문은 생각도 못했는데, 어차피 i,j를 기준으로 칸에 있는 숫자만큼 이동하면되니까 i와 j가 순서대로 움직여도 상관없을 것 같다

이부분 빼면 안된다. 이걸 빼면 (n-1,n-1)도 카운트 돼서 dp[-1][-1]값이 4배가 된다. 

if i==n-1 and j==n-1:
            break

-정답풀이

n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))
dp=[[0]*n for _ in range(n)]
dp[0][0]=1
for i in range(n):
    for j in range(n):
        if i==n-1 and j==n-1:
            break
        if i+data[i][j]<n:
            dp[i+data[i][j]][j]+=dp[i][j]
        if j+data[i][j]<n:
            dp[i][j+data[i][j]]+=dp[i][j]
print(dp[-1][-1])

-시도해본 풀이

n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))
dp=[[0]*n for _ in range(n)]
dx=[0,1]
dy=[1,0]

def dfs(x,y):
    if data[x][y]==0:
        dp[x][y]+=1
        return 1
    for i in range(2):
        nx,ny=dx[i]*data[x][y]+x,dy[i]*data[x][y]+y
        if 0<=nx<n:
            dfs(nx,y)
        if 0<=ny<n:
            dfs(x,ny)
    return dp[-1][-1]
print(dfs(0,0))

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

이전에 싸피 준비할 때 들었던 유튜브 강의에서 같은 내용을 공부한 적이 있어서 문제 보자마자 가장 긴 증가하는 부분수열 문제라는 것을 알았다. 

주어진 정보를 0열을 기준으로 sort한 다음 1열 값과 dp값을 이용해서 가장 긴 부분수열의 길이를 구한다음,

전체 가짓수에서 빼주면 답이다. 

한번에 맞혔던 문제!

-정답풀이: 

n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))
data.sort()
dp=[0]*501
for i in range(n):
    for j in range(i+1):
        if data[j][1]<data[i][1] and dp[j]>dp[i]:
            dp[i]=dp[j]
    dp[i]+=1
x=max(dp)
print(n-x)

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

처음에 n=1,2,3,4일 때 값을 3,7,15,38으로 구해서 점화식을 못 구했지만

다시 갯수 세보니 3,7,17,41이어서 f(n)= 2*f(n-1)+f(n-2)의 점화식을 구했다

답을 구한후 9901로 나눠줘야한다

-정답풀이 1:

n=int(input())
dp=[0 for _ in range(n+1)]
dp[0]=1
dp[1]=3

if n==1:
    print(dp[1])
else:
    for i in range(2,n+1):
        dp[i]=(2*dp[i-1]+dp[i-2])%9901
    
    print(dp[n])

-정답풀이 2: 

n=int(input())
dp=[0 for _ in range(100001)]
dp[1]=3
dp[2]=7

for i in range(3,n+1):
    dp[i]=(2*dp[i-1]+dp[i-2])%9901
    
print(dp[n])

이렇게 풀면 indexerror난다. n==1일 때는 dp=[0,0]으로 인덱스가 1까지 밖에 없는데, 네번째줄에 인덱스 2에 7을 넣기 때문에 indexError가 날 수 밖에 없다.

아래처럼 하고 싶다면 dp를 n+1개의 원소만 생성하는 것 대신, dp=[0]*100001로 초기화하고, dp[-1]이 아닌 dp[n]을 출력하면된다.

n=int(input())
dp=[0]*(n+1)
dp[1]=3
dp[2]=7

for i in range(3,n+1):
    dp[i]=(2*dp[i-1]+dp[i-2])%9901
    
print(dp[-1])

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