수학과의 개발자 도전기

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

풀이 보면서 정수 삼각형이랑 비슷하다고 느낀 문제. 

처음에는 점화식이 dp[i]=dp[i-1]*2-1이라고 생각했는데 바로 틀렸다. 

이는 숫자에서 +-1을 하는데, 0은 -1이 안되므로 1밖에 없고, 9도 +1하면 10이라서 안되니까 8밖에 없어서 

0과 9일 때 제외는 모든 이전 자리수에서 가져오면 된다. 

-정답 풀이

n=int(input())
dp=[[0 for _ in range(10)] for _ in range(101)] 
for i in range(1,10):
    dp[1][i]=1
for i in range(2,n+1):#2부터 n자리 수까지
    for j in range(10): #0부터 9에 대해서 진행
        if j==0:
            dp[i][j]=dp[i-1][1]
        elif j==9:
            dp[i][j]=dp[i-1][8]
        else:
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]
print(sum(dp[n])%(10**9))

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

이전에 풀었던 계단 올라가기와 동일한 문제인데 다른점은 꼭 마지막 와인을 마시지 않아도 된다는 것. 

그래서 점화식에 추가할 것이 있다. 현재 와인을 마시지 않았을 조건(dp[i-1])

이에 대한 자세한 설명은 여기서 볼 수 있다.

https://www.acmicpc.net/board/view/60664

dp[i]=max(dp[i-3]+data[i-1]+data[i],dp[i-2]+data[i],dp[i-1])

이 외에는 계단 올라가기와 동일하다. 

그동안 IndexError가 발생했던 이유가, n에 따라 data와 dp 리스트를 생성하면

n==1, n==2일 때는 숫자가 모자라서 for문을 못 돌린다. 그래서 조건에 따라 if, elif문을 작성하면 된다 

n=int(input())
data=[]
for _ in range(n):
    data.append(int(input()))
if n==1:
    print(data[0])
elif n==2:
    print(data[0]+data[1])
else:    
    dp=[0]*n
    dp[0]=data[0]
    dp[1]=data[1]+data[0]
    dp[2]=max(data[2]+data[0],data[2]+data[1],dp[1]) #dp[2]=dp[1]은 2번째 와인을 마시지 않았다는 말
    for i in range(3,n):
        dp[i]=max(dp[i-3]+data[i-1]+data[i],dp[i-2]+data[i],dp[i-1])
    
    print(max(dp))

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