[코딩테스트] #11. 백준 12865번, 11054번, 1699번 -> 다시 복습하기

1. 12865번: 평범한 배낭 

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

12865번: 평범한 배낭

어려웠던 문제

 

-정답 풀이: 

• item에는 문제 값 대입(인덱스0에는 물건의 무게가, 인덱스1에는 물건의 가치가 들어있다)
• N[0],K[0]에는 0값을 넣어준다 -> (N+1)x(K+1) 행렬인 dp 생성 

 

• i번째 물건의 무게가 남은 무게보다 작을때 가치값 변경됨 
• 당연히 i번째 물건의 무게가 오버되면 가방에 넣을 수 없으므로 이전행값과 동일하게된다(else문)
• 점화식: dp[i][j]=max(dp[i-1][j],dp[i-1][j-item[i][0]]+item[i][1]) -> 점화식 아직 이해 안갔음

 

 

2. 11054: 가장 긴 바이토닉 부분 수열

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

11054번: 가장 긴 바이토닉 부분 수열

가장 긴 수열 구하는 문제를 알면 풀  수 있는 문제.

 

-정답풀이: 

 

• 증가하는 수열부분

 

• 감소하는 수열부분
• 끝부분부터 거꾸로 진행하면 감소하는 부분도 결국 증가하는 부분과 같은 풀이를 가지게 된다

 

 

3. 1699: 제곱수의 합

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

1699번: 제곱수의 합

이것도 어려웠던 문제다

 

-정답풀이:

 

• 8번 9번 점화식이 아직 이해가 가지 않는다. 추후로 더 봐야할 것 같다