[백준11055] / 가장 큰 증가하는 부분 수열 - DP

2024. 9. 21. 18:33·Programming/Algorithm

 

백준11055

 

푼 날짜 : 2024.09.21

푼 문제 : [11055] / 가장 큰 증가하는 부분 수열

사용한 언어 : python

알고리즘 : DP

 

 

점화식:

dp[i] = max(dp[i], dp[j]+lst[i]) (if lst[j] < lst[i])

 

여기서 뽀인트🌟 는 i번째 반복이 끝날 때 현재 dp[i]와 lst[i]를 비교해서 큰 값을 넣어주는 것!

안그러면 lst[i]는 0보다 큰 수 인데 dp[i]에는 0이 들어가 있게 된다.

 

이렇게 되면 다음 계산에 영향을 준다!!

 

 

 

코드 :

import sys

N = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))
dp = [0 for _ in range(N)]
dp[0] = lst[0]

for i in range(1, N):
    for j in range(i):
        if lst[j] < lst[i]: 
            dp[i] = max(dp[i], dp[j]+lst[i])
    dp[i] = max(dp[i], lst[i])

print(max(dp))

 

 

오늘도 1솔 성공 ^____^

 

 

'Programming > Algorithm' 카테고리의 다른 글

[백준2749] / 피보나치 수 3 - 분할정복, 거듭제곱, DP (feat. 피사노 주기)  (0) 2024.10.02
[백준11659] / 구간 합 구하기 4 - 누적합  (2) 2024.09.26
[백준9465] / 스티커 - DP  (1) 2024.09.14
[백준1149] / RGB거리 - DP  (0) 2024.09.13
[백준1303] / 전쟁 - 전투 - DFS  (0) 2024.09.11
'Programming/Algorithm' 카테고리의 다른 글
  • [백준2749] / 피보나치 수 3 - 분할정복, 거듭제곱, DP (feat. 피사노 주기)
  • [백준11659] / 구간 합 구하기 4 - 누적합
  • [백준9465] / 스티커 - DP
  • [백준1149] / RGB거리 - DP
__narrrrrmm
__narrrrrmm
__narrrrrmm
낢
__narrrrrmm
글쓰기 관리
전체
오늘
어제
  • 분류 전체보기 (71)
    • Programming (68)
      • Algorithm (61)
      • React JS (2)
      • SQL (5)
    • 낢의 하루 (1)
    • 대외활동 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

mysql
웹동아리
백준
알고리즘
MST
DFS
heic
BFS
PCCP
다이나믹프로그래밍
SQL
투포인터
그래프탐색
DP
누적합
Python
StarRating
최소스패닝트리
파이썬
Dijkstra
그래프
백트레킹
React.js
삼성 금융아카데미
컬럼별칭
백트래킹
Javascript
다익스트라
파싱
프로그래머스
hELLO· Designed By정상우.v4.5.3
__narrrrrmm
[백준11055] / 가장 큰 증가하는 부분 수열 - DP
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.