미소를뿌리는감자의 코딩
[백준 2024/10/04] 11055번 가장 큰 증가하는 부분 수열 본문
728x90
1. 문제
https://www.acmicpc.net/problem/11055
2. 접근 방법
처음에는 위와 같이 구상하였다.
현재 idx에서 이전 idx를 비교를 하면서 0번 idx까지 내려간다. 만약 값이 현재 idx value 보다 작다면, max(inc[idx], inc[idx] + arr[i])
를 진행해준다. max를 이용하는 이유는 더 앞에서 현재 값보다 더 큰 값을 지니고 있는 증가하는 수열이 있을 수 있기 때문이다.
처음에는 현재 idx보다 작은 값을 찾으면 바로 값을 더해주고 break를 해주었다.
하지만
[10, 22, 9, 33, 21, 50, 41, 60, 80]
[1, 2, 1, 2 ### 3 이 들어가야 함.
증가하는 수열의 길이를 파악하는 과정을 보면, 만약, 현재 idx보다 작을 시, break를 한다면 33의 경우 2의 값을 지니게 된다.
하지만, 더 앞을 탐색하면, 10 - 22 - 33 으로 3의 값을 가질 수 있다. 따라서 0번 idx까지 탐색을 해주어야 한다.
3. 코드
import copy
def max_val(arr, inc_a, n):
for i in range(1, n, 1):
for j in range(i-1, -1, -1):
if arr[j] < arr[i]:
inc_a[i] = max(inc_a[i], inc_a[j] + arr[i])
return max(inc_a)
if __name__ == "__main__":
n = int(input())
arr = list(map(int, input().split()))
inc_a = copy.deepcopy(arr)
print(max_val(arr, inc_a, n))
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/10/09] 14501번 퇴사 (0) | 2024.10.09 |
---|---|
[백준 2024/10/07] 10844번 쉬운 계단 수 (0) | 2024.10.07 |
[백준 2024/10/02] 2098번 외판원 순회 (0) | 2024.10.03 |
[백준 2024/10/01] 11049번 행렬 곱셈 순서 (1) | 2024.10.01 |
[백준 2024/09/30] 1931번 회의실 배정 (0) | 2024.09.30 |