난이도 : 실버2
소요시간 : 27m
사용한 풀이법 : DP
풀이 과정
- 입력받은 문자열을 정수형 리스트 arr[]로 변환
- dp[]에는 해당 인덱스에서 가질 수 있는 최대값을 넣는다
- dp[i-1]+arr[i]가 음수일 경우 최대값 생성에 방해가 되므로 해당 dp값은 0으로 초기화
- 원래는 여기서 풀이를 끝낼라했는데 모두 음수일 경우를 고려안하게 생각나서 dp첫번째 조건문 뒤에 arr값을 dp값으로 초기화 해주는 코드 추가 ⇒ 내가 생각해도 좀 후진 코드..ㅎ
- 원래는 max(dp)를 하려했으나 위 코드 추가되면서 max(arr)로 변경
다른 풀이
- 입력받은 문자열을 정수형 리스트 arr[]로 변환
- 현재합과 최대합 연산용 변수 선언
- arr을 돌면서 해당 인덱스와 해당 인덱스에 현재합을 더한 것중 max를 현재합에 대입
- 다시 max연산을 통해 최대합 도출
작성 코드
n=int(input())
dp=[0]*n
arr = list(map(int,input().split()))
dp[0] = arr[0]
for i in range(1,n):
if dp[i-1] + arr[i] > 0:
dp[i] = dp[i-1]+arr[i]
arr[i] = dp[i-1]+arr[i]
else :
dp[i] = 0
print(max(arr))
#2차 코드
n = int(input())
arr = list(map(int, input().split()))
max_sum = arr[0]
current_sum = arr[0]
for i in range(1, n):
current_sum = max(arr[i], current_sum + arr[i])
max_sum = max(max_sum, current_sum)
print(max_sum)
'알고리즘' 카테고리의 다른 글
[자료구조] 이진 트리 & 힙 (0) | 2024.03.27 |
---|---|
[자료구조] 연결 리스트 & 스택 (0) | 2024.03.26 |
백준 #1699 <제곱수의 합> (0) | 2024.03.09 |
백준 #1463 <1로 만들기> (0) | 2024.03.08 |
백준 #9095: 1,2,3 더하기 (1) | 2024.03.06 |