DP 알고리즘 학습

2579. 계단오르기

핵심조건
1. 마지막 계단 밟아야함
2. 1,2칸 오를 수 있음
3. 연속 3칸 x

• 최대 점수를 얻는 경로를 구해야하고 최대 점수 출력해야함.

접근 방식
1. 상태 정의
dp[i] = i번째 계단을 밟았을때의 최대 점수

2. 점화식 설계
   i번째 밟는 방법
   1) i-2 => i (한칸 건너뜀)
   2) 연속할 경우는 i-3 -> i-1 -> i 일 경우

#dp 초기값 설정 
#점화식 
#1. 계단 점수 입력 받기
import sys 
input = sys.stdin.readline
N = int(input()) 
score = [0] *(N+1) 
for i in range(1, N+1): 
	score[i] = int(input()) 
    
dp = [0] * (N+1) 
#초기값 
dp[0] = 0 
dp[1]= score[1]
dp[2] = score[2]

#점화식 
for i in range(3, N+1): 
	dp[i] = max(score[i] + dp[i-2], score[i] + score[i-1] + dp[i-3])

print(dp[N]]

=> 조건 분기 x dp[2] = score[1] + score[2]

import sys 
input = sys.stdin.readline
N = int(input()) 
score = [0] + [int(input()) for _ in range(N)]

#print(score)
dp = [0] * (N+1) 

#초기값 별도 처리 !!
if N >= 1: 
	dp[1] = score[1]
	
if N >=2: 
	dp[2] = score[1] + score[2]

#점화식 
for i in range(3, N+1): 
	dp[i] = max(score[i] + dp[i-2], score[i] + score[i-1] + dp[i-3])

print(dp[N])

11052. 카드 구매하기

• dp + 완전 탐색
  문제:
  카드팩을 골라 카드 N장을 만들고, 지불 금액 최대화

핵심 조건

• 중복사용 가능
• 총 카드 수는 N개
• 최대한 많은 지불 금액

알고리즘

• 조합 -> 시간 초과
• 최대값을 누적해 구해야함.
• 부분 문제 -> dp로 풀어야하네

dp[i] = i장을 만들기 위해 지불할 수 있는 최대 금액
점화식으로 표현
dp[i] =j는 1~i까지 증가
dp[i] = dp[i-j] + lst[j]임.

33886. 카드 뭉치

-> 나중에

2417. 정수 제곱근

• 이분 탐색
  정수 N이 주어졌을때 어떤 정수 X의 제곱이 N이상이 되는 가장 작은 X 구하기. X^2 >=N을 만족하는 최소 X찾기

• 브루트포스 -> 시간 초과

• logN 수준의 알고리즘 -> 이분 탐색 알고리즘.

이분탐색 아이디어

#변수
left = 0, right = N
mid 변수
#조건 분기

N = int(input()) 

left = 0 
right = N 
while left <=right: 
	mid= (left + right) //2 
    
    if mid* mid >= N: 
    	result = mid 
    	right = mid-1
    else: 
    	left = mid+1 
print(result)

2343. 기타레슨

이분탐색 + 그리디
-> 이해 x

11053. 가장 긴 증가하는 부분 수열

N = int(input()) 
lst = list(map(int, input().split()))

#길이 1로 초기화 
dp = [1] * N 
for i in range(N): 
	for j in range(i): 
    	dp[i] = max(dp[i], dp[j] +1)
result = max(dp) 
print(result)