[코딩테스트] #9. 백준 9461번,14051번, 9465번

1. 9461번: 파도반 수열 

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

9461번: 파도반 수열

수열이 1,1,1,2,2,3,4,5,7,9로 진행되는 것에 기반해서 점화식까지 구하는 건 성공함.오늘 풀었던 세문제 중 가장 쉬웠던 문제

-점화식: P(N)= P(N-5)+P(N-1)

 

 

-정답풀이 : 

-틀린 풀이1:

• 4번에 i를 j로 바꿔야함(이거때문에 뻘짓함. NameError 조심)

 

-틀린 풀이2:

 

• dp에 숫자 모두 입력되고, 거기서 출력하는것이 맞음

 

2. 14051번: 퇴사 (여러번 반복해서 봐야할 문제)

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

14501번: 퇴사

0번째 컬럼부터 생각하고 알고리즘 설정하려고 했는데 이게 아니라 마지막 컬럼을 기준으로 풀어나가야하는 문제 

 

-정답풀이: 

n=int(input())
T=[]
P=[]
dp=[]

for i in range(n):
    x,y=map(int,input().split())
    T.append(x)
    P.append(y)
    dp.append(y)
    
dp.append(0)#n번째 인덱스에 0대입 

for i in range(n-1,-1,-1):
    if T[i]+i>n:#일이 퇴사후까지 진행되면 다음으로 넘김
        dp[i]=dp[i+1]
    else:
        dp[i]=max(dp[i+1],P[i]+dp[i+T[i]])
print(dp[0])

:여기서 왜 dp[i+T[i]]가 나오는지 이해가 가지 않는다 

 

 

3. 9465번: 스티커 

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

9465번: 스티커

이것도 어려웠던 문제 대각선으로 값을 더해야하는 건 알겠는데 어떻게 진행해야하는지 몰랐던 문제. 

 

-정답풀이:

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