수학과의 개발자 도전기

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

전에 스스로 푼 문제였는데 이번에도 스스로 푼 문제였다 

점화식 구하기 위해서 n==1, n==2, n==3일 때 구체적은 상황을 작성해봤다. 

그랬더니 dp[i][j]=dp[i][j-1]-dp[i-1][j-1]이라는 점화식을 구한후 코드로 옮겼다 

-정답풀이 

정답 제출 전에 잔잔바리 실수가 있었다

• for i in range(2,n+1) 인데, for i in range(1,n+1)로해서 틀렸고 
• 점화식 그대로 안 옮기고 dp[i][j-1]+dp[i-1][j-1]로 작성해서 틀렸고
• 출력 할 때 dp[-1][-1]로 출력해서 틀렸고, 
• 기껏 sum(dp[-1]) 출력했는데 10007로 나눈 나머지로 출력해야 됐어서 틀렸었다;;; 

n=int(input())
dp=[[0]*10 for _ in range(n+1)]
for i in range(10):
    dp[1][i]=1
    
for i in range(2,n+1):
    for j in range(10):
        if j==0:
            dp[i][j]=sum(dp[i-1])
        else:
            dp[i][j]=dp[i][j-1]-dp[i-1][j-1]
print(sum(dp[-1])%10007)

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

기억에 의존하긴 했지만, 스스로 푼 문제다 

주어진 단어 길이들로 2차원 행렬을 만든뒤, 완전 탐색으로 문자가 같은 경우와 아닌경우에 대한 점화식을 세우고 

코드로 점화식을 구현하면 된다.

점화식

LCS(x[i],y[j]) = LCS(x[i-1],y[j-1])+1 (if x[i]==y[j])

                       = max(LCS(x[i-1],y[j]),LCS(x[i],y[j-1])) (if x[i] != y[j])

초기화를 하는게 약간 어려웠는데, 0행과 0열을 기준으로 같은 문자인 경우만 1로 바꾸면 된다고 생각했는데 틀린 답은 출력했다. 원래는 4를 출력해야하는데 3을 출력함 

원인을 생각해보니 3행 0열에는 0이 아니라 1이 있어야 한다. 앞에 A로 같은 문자가 있는게 누적돼야하므로 

근데 이를 누적하지 않아서 4가 아닌 3이 출력된 것 같다. 

그래서 0행과 0열에 대해서 값 비교 및 누적을 먼저 한 후 나머지에 대해서 연산을 했더니 정답으로 떴다 

-정답풀이 

x=list(input())
y=list(input())
n=len(x)
m=len(y)
dp=[[0]*n for _ in range(m)]

if x[0]==y[0]:
    dp[0][0]=1
else:
    dp[0][0]=0
    
for i in range(1,n):
    if x[i]==y[0]:
        dp[0][i]=1
    else: 
        dp[0][i]=dp[0][i-1]
        
for j in range(1,m):
    if y[j]==x[0]:
        dp[j][0]=1
    else:
        dp[j][0]=dp[j-1][0]

for i in range(1,m):
    for j in range(1,n):
        if y[i]==x[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
            
print(dp[-1][-1])

-더 짧은 풀이 

import sys

s1=sys.stdin.readline().strip().upper()
s2=sys.stdin.readline().strip().upper()
len1=len(s1)
len2=len(s2)
dp=[[0 for i in range(len2+1)] for j in range(len1+1)]
#i==0, j==0일 때는 dp값 0 + 글자수니까 전체 행렬 길이= 글자길이+1

for i in range(1,len(s1)+1):
    for j in range(1,len(s2)+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
print(dp[-1][-1])

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

처음에 bfs로 풀어야하나 싶었는데 이걸로 풀면 안되는게 

상,하,좌,우의 값을 확인하는 것이 아니라 이것들을 빼고 진행하는 거라서 탐색으로 진행하면 안된다 

인덱스에 따라서 더할 수 있는 값들 중 최댓값을 더해가다가 마지막 열의 두 값 중 더 큰 값을 출력하면 된다 

아직 스스로 푼건 아니지만, 다이나믹 프로그래밍 문제를 풀면서 느낀게 값을 누적하고, 최댓값을 적용해야하는 상황을 잘 판단해야지 문제를 잘 풀 수 있겠다 라는 생각을 한다

-정답풀이 

t=int(input())
for _ in range(t):
    n=int(input())
    data=[]
    for _ in range(2):
        data.append(list(map(int,input().split())))
    for j in range(1,n):
        if j==1:
            data[0][j]+=data[1][j-1]
            data[1][j]+=data[0][j-1]
        else:
            data[0][j]+=max(data[1][j-1],data[1][j-2])
            data[1][j]+=max(data[0][j-1],data[0][j-2])
    print(max(data[0][n-1],data[1][n-1]))

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

이 문제는 이제 3번째 푸는 거라서 어떻게 풀지 대충 기억이 났다. 

우선 주어진 정보를 역순으로(range(n-1,-1,-1)) 진행한다 

-틀린 풀이

i번째 날일 때 일을하고, 일이 끝날 때(t[i]+i) 주어진 날(n+1)을 벗어나지 않는 경우는 새로운 값을 누적하는 것이라고 생각했는데,

여기에 추가해서 값을 비교한 후 더 큰것을 dp[i]에 넣어야한다  

그리고 일이 끝날 때 주어진 날을 벗어나는 경우에 대해서 생각하지 못했다

n=int(input())
t=[]
p=[]
dp=[0]*(n+1)
for _ in range(n):
    a,b=map(int,input().split())
    t.append(a)
    p.append(b)
    
for i in range(n-1,-1,-1):
    if t[i]+i <(n+1):
        dp[i]=dp[t[i]+i]+p[i]
        
print(max(dp))

-정답풀이 

n=int(input())
t=[]
p=[]
dp=[0]*(n+1)
for _ in range(n):
    a,b=map(int,input().split())
    t.append(a)
    p.append(b)
    
for i in range(n-1,-1,-1):
    if t[i]+i <(n+1):
        dp[i]=max(dp[i+1],dp[t[i]+i]+p[i])
    else:
        dp[i]=dp[i+1]
        
print(dp[0])