1. 9461번: 파도반 수열
-문제: https://www.acmicpc.net/problem/9461
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
수열이 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번: 퇴사
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
www.acmicpc.net
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가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의
www.acmicpc.net
이것도 어려웠던 문제 대각선으로 값을 더해야하는 건 알겠는데 어떻게 진행해야하는지 몰랐던 문제.
-정답풀이:
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]))'백준 > DP' 카테고리의 다른 글
| [코딩테스트] #11. 백준 12865번, 11054번, 1699번 -> 다시 복습하기 (0) | 2021.12.22 |
|---|---|
| [코딩테스트]#10. 백준 9251번,11057번, 2293번 (0) | 2021.12.20 |
| [코딩테스트]#8. 백준 1010번,11052번,1904번 (0) | 2021.12.17 |
| [코딩테스트] #7. 백준 10844번,2193번,11727번 (0) | 2021.12.14 |
| [코딩테스트]#6. 백준/다이나믹프로그래밍/ 1912번,2156번, 2748번 (0) | 2021.12.13 |
