수학과의 개발자 도전기

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

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

점화식은 전에 알고 있어서 크게 어려지 않았는데, 맞지막에 답 출력할 때 10007로 나누는 거를 안해서 틀렸다

출력 조건 정확히 기억하기!!

-정답 풀이 

n=int(input())
dp=[0]*1001
dp[1]=1
dp[2]=2
for i in range(3,n+1):
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%10007)

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

점화식을 이용해서 풀어야하는 것은 알고 있었지만 1,2,3으로만 숫자 구성해야하는 거를 간과함

그래서 f(1)=1, f(2)=1, f(3)=3으로 생각해서 점화식이 이상하게 나왔음 

근데 1,2,3은 각각 1,2,3으로도 구성 가능하므로 f(1)=1, f(2)=2, f(3)=4 이다 

따라서 점화식은 f(n)=f(n-1)+f(n-2)+f(n-3)

이거를 통해서 만든 풀이는 다음과 같다 

-정답풀이

t=int(input())
for _ in range(t):
    dp=[0]*12
    n=int(input())
    dp[1],dp[2],dp[3]=1,2,4
    if n<=3:
        print(dp[n])
    else:
        for i in range(4,n+1):
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
        print(dp[n])