수학과의 개발자 도전기

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

-정답풀이:

(max(dp[i]+data[i+1],data[i+1])): 이 식은 값을 누적했을 때와, 새로 시작했을 때의 값 중에 최댓값을 dp에 저장한다 

n=int(input())
data=list(map(int,input().split()))
dp=[data[0]]
for i in range(n-1):
    dp.append(max(dp[i]+data[i+1],data[i+1]))
print(max(dp))

-메모리 초과 

nxn dp 행렬에서 i번째 시작해서 j번째 까지의 합을 모두 구해서 

각 행에서 최댓값을 찾고, 그 중에서 최댓값을 찾으면 된다고 생각했는데 

메모리가 128MB라서 메모리 초과가 난 것 같다 

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

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

-정답풀이:

dp에는 각 수열의 길이를 저장한다 

0부터 i까지의 수 중에서 data[i]보다 작지만, 수열에 들어간 j가 있을 때 dp[j]값을 누적하다가 반복문이 끝나면 data[i]는 

수열에 들어가니까 dp[i]+=1을 해준다 

마지막에 dp의 최댓값 출력하는 거 잊지말기!

n=int(input())
data=list(map(int,input().split()))
dp=[0]*n
for i in range(n):
    for j in range(i+1):#0부터 i까지
        if data[j]<data[i] and dp[j]>dp[i]:
            dp[i]=dp[j]#i전에 if문을 만족하는게 여러개 있으니까 그거를 누적하는 것
    dp[i]+=1
print(max(dp))

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

-정답풀이

• i-1번째 계단에서 온 경우. 이때는 i-3 -> i-1 ->i 의 루트를 거쳐야 한다. 이유는 한칸씩 연속으로 3번 오는 거를 피하기 위해서다
• i-2번째 계단에서 온 경우 이미 한칸씩 연속 세번 올 경우는 없으므로 i-2 -> i 의 루트를 생각하면 된다

위 과정을 기반으로 코드를 작성하면 다음과 같다 

n=int(input())
data=[0]
for _ in range(n):
    data.append(int(input()))
if n==1: #이거를 빼면 indexError가 발생한다
    print(data[1])
else:    
    dp=[0]*(n+1)    
    dp[1]=data[1]
    dp[2]=data[2]+data[1]

    for i in range(3,n+1):
        dp[i]=data[i]+max(dp[i-3]+data[i-1],dp[i-2])
    
    print(dp[n])

-삽질 기록

이전에 풀었던 기억으로 i번째 계단으로 올라왔다면 두가지 경우가 있다 

• i-1번째 계단에서 온 경우. 이때는 i-3 -> i-1 ->i 의 루트를 거쳐야 한다. 이유는 한칸씩 연속으로 3번 오는 거를 피하기 위해서다
• i-2번째 계단에서 온 경우 i-3 -> i-2 -> i의 경로를 생각했다. 근데 굳이 그럴 필요가 없이 i-2 -> i 경로만 생각하면 된다 

나름 점화식 생각한다고 했는데 오류가 많다 

data[i]= data[i-3] + max(data[i-1],data[i-2]) # 잘못된 점화식
dp[i]= data[i]+max(dp[i-3]+data[i-1],dp[i-2]) #이걸로 고쳐야함

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

-정답 풀이: 

그동안 풀어본 dp문제는 i에서 i+1로 가는 방향이 아니라 i번째가 i-1번째 와 i-2번째로부터 들어오는 방향으로 생각하는 풀이가 많았다. 그래서 i번째 집이 있을 때 그것의 열에 따라 그 열을 제외한 열 중에 최솟값을 누적해 가는 방법으로 풀었더니 정답이 나왔다 

처음에 min를 data로 했을때 틀렸는데,

min(data[i-1][1],data[i-1][2])

이는 dp에 그동안의 합을 누적해야 하므로 min에 data가 아닌 dp를 써야한다 

min(dp[i-1][1],dp[i-1][2])

첫번째 풀었을 때는 엄청 어려웠는데, 2번째 푸니까 풀만하다 

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

for i in range(1,n):
    dp[i][0]=data[i][0]+min(dp[i-1][1],dp[i-1][2])
    dp[i][1]=data[i][1]+min(dp[i-1][0],dp[i-1][2])
    dp[i][2]=data[i][2]+min(dp[i-1][1],dp[i-1][0])
    
print(min(dp[n-1]))