수학과의 개발자 도전기

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

완전 탐색으로 하면 되는 쉬운 문제인 줄 알았는데, 시간 초과가 떴다.

그래서 찾아보니 dp로 (0,0)부터 (i,j)까지의 합을 저장한후 이를 이용하는 문제였다

이 풀이에서 가장 이해가 안가는 부분이다.

i+1,j+1까지의 합을 구하면 data[i][j]가 아니라 data[i+1][j+1]을 더해야 하는게 아닌가? 싶은 생각인데

실제 행렬 위치와 주어진 행렬 위치가 다르므로 그걸 생각해서 한 것같다. 이 부분은 좀 더 해봐야 할 것 같다

#(0,0)부터 (i,j)까지의 합이 dp[i+1][j+1]에 저장됨
        dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]-dp[i][j]+data[i][j]

-정답풀이:

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        #(0,0)부터 (i,j)까지의 합이 dp[i+1][j+1]에 저장됨
        dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]-dp[i][j]+data[i][j]
for _ in range(m):
    a,b,c,d=map(int,input().split())
    print(dp[c][d]-(dp[c][b-1]+dp[a-1][d]-dp[a-1][b-1]))

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

도전히 인자 3개인 dp를 못 구할 것 같았는데 3중 리스트를 만들면 된다는 걸 깨달았다.

그러고 함수 w를 생성할 생각은 못했다. 

그래도 일단 자료구조라도 생각해낸게 발전한 것 같다

-정답풀이:

dp=[[[0]*21 for _ in range(21)] for _ in range(21)]

def w(a,b,c):
   
    if a<=0 or b<=0 or c<=0:
        return 1
    if a>20 or b>20 or c>20:
        return w(20,20,20)
        
    if dp[a][b][c]: #여기
        return dp[a][b][c]
    elif a<b<c:
        dp[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)
        return dp[a][b][c]
    else:
        dp[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)
        return dp[a][b][c]

while True:
    a,b,c=map(int,input().split())
    if a==-1 and b==-1 and c==-1:
        break
    print(f'w({a}, {b}, {c}) = {w(a,b,c)}')

-시도해본 풀이

while True:
    a,b,c=map(int,input().split())
    if a==-1 and b==-1 and c==-1:
        break
    if a<=0 or b<=0 or c<=0:
        dp[a][b][c]=1
    if a>20 or b>20 or c>20:
        dp[a][b][c]=dp[20][20][20]
    if a<b<c:
        dp[a][b][c]=dp[a][b][c-1]+dp[a][b-1][c-1]-dp[a][b-1][c]
    else:
        dp[a][b][c]=dp[a-1][b][c]+dp[a-1][b-1][c]+dp[a-1][b][c-1]-dp[a-1][b-1][c-1]
    print(w(a,b,c) = dp[a][b][c])

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

-정답풀이: 

LCS와 풀이는 같은데 다만 숫자가 아닌 문자를 dp에 넣으면 된다

x=['']+list(input())
y=['']+list(input())
dp=[['']*len(y) for _ in range(len(x))]

for i in range(1,len(x)):
    for j in range(1,len(y)):
        if x[i]==y[j]:
            dp[i][j]=dp[i-1][j-1]+x[i]
        else:
            if len(dp[i-1][j])>=len(dp[i][j-1]):
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=dp[i][j-1]
result=dp[-1][-1]                
print(len(result))
print(result)

-문제:

-정답풀이:

n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))

dx=[-1,1,0,0]
dy=[0,0,-1,1]
dp=[[0]*n for _ in range(n)]
def dfs(x,y):
    if dp[x][y]: #여기
        return dp[x][y] #여기
    dp[x][y]=1 #여기
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if data[x][y]< data[nx][ny]:
                dp[x][y]=max(dp[x][y],dfs(nx,ny)+1) #지금까지 온 칸 수와 이동했을 때 칸 개수 비교
    return dp[x][y]   

answer=0                
for i in range(n):
    for j in range(n):
        answer=max(answer,dfs(i,j))
                        
print(answer)