백준 1912번 연속합
어렵다
접근방법이 지금까지 했던 dp랑은 또 다른 느낌이다
중요한건 구간합이라는거 같은데...
n도 10^5이라서 n^2으로 풀면 안된다...
그러면 오래 걸려봐야 O(nlogn)으로 풀린다는 건데...
nlogn보다는 일렬 순회해서 O(n)으로 푸는게 맞는거 같다.
이제 접근법을 좀 생각해보자
앞에서 부터 더해 나가는데 그 뒷 숫자와의 합계가 이전 max값보다 낮다면 갱신을 포기하고 다시 0(인덱스를 의미하는게 아님 합계를 의미함)부터 검사시작하는 방식이 맞을 것 같다.
결과값을 저장하고 또 부분수열의 합을 계산을 따로 해주는 방식으로 풀면 정답일듯하다.
import sys
n=int(sys.stdin.readline().rstrip())
a=[]
a=list(map(int,sys.stdin.readline().rstrip().split()))
result=a[0]
prev_sum=a[0]
for i in range(1,n):
if prev_sum+a[i]>=prev_sum:
prev_sum+=a[i]
else:
prev_sum=0
if prev_sum>result:
result=prev_sum
print(result)
그래서 이렇게 작성했는데 테스트 케이스 첫번째는 통과되는데 나머지 두개는 통과가 안된다
주된 이유는
부분수열이 음수를 포함하고 있다는 것과
prev_sum을 0으로 만들어버려서 음수들만 입력이 들어왔을때 대처되지 않는다는것이다.
그래서 접근을 살짝 다르게 하기로 했다.
음수가 올때까지 무조건 합연산을 한 다음 음수까지 합한값이 0보다 작으면 초기화 하는 방식으로 변경하기로 했다.
3번째 케이스에 대해서는 조금 있다가 다시 하자.
import sys
n=int(sys.stdin.readline().rstrip())
a=[]
a=list(map(int,sys.stdin.readline().rstrip().split()))
result=a[0]
prev_sum=a[0]
for i in range(1,n):
if prev_sum+a[i]>=0:
prev_sum+=a[i]
else:
prev_sum=0
if prev_sum>result:
result=prev_sum
print(result)이렇게 수정하니 2번째 테스트 케이스까지는 맞게 나온다.
이제 3번째 테스트케이스에 대해서 생각을 해봐야 하는데
전부 음수가 나올때가 문제이다.
그렇다면 result가 0일때 그냥 최대값을 한번 찾아보면 되지않을까?싶어졌다.(result가 0이라는건 양수입력이 한개도 없다는 뜻이므로)
그래서 완성된 코드
import sys
n=int(sys.stdin.readline().rstrip())
a=[]
a=list(map(int,sys.stdin.readline().rstrip().split()))
result=a[0]
prev_sum=a[0]
for i in range(1,n):
if prev_sum+a[i]>=0:
prev_sum+=a[i]
else:
prev_sum=0
if prev_sum>result:
result=prev_sum
if result<=0:
min_value=a[0]
for i in range(n):
min_value=max(min_value,a[i])
result=min_value
print(result)이대로 제출해보자
놓친게 있는듯 하다.
도저히 모르겠어서 요즘핫한 딥시크쨩에게 물어보았다
길어....
반례만 물어봐야했는데 그냥 왜 틀렸냐고 물어봐서 정답코드까지 알려준모양이다...
문제가 prev_sum갱신인건 알았는데 왜 문제가 되는지를 모르겠는데
import sys
n=int(sys.stdin.readline().rstrip())
a=[]
a=list(map(int,sys.stdin.readline().rstrip().split()))
result=a[0]
prev_sum=a[0]
for i in range(1,n):
if prev_sum+a[i]>=0:
prev_sum+=a[i]
else:
prev_sum=a[i]
result=max(prev_sum,result)
print(result)이코드도 오답이다...
왜지?
깨달았다
[-5,7,-4,-2]의 경우 답으로 2가 나와버린다
0보다 크거나 같다가 아니라 a[i]보다 큰지 검사하면 해결되는 문제였다...
import sys
n=int(sys.stdin.readline().rstrip())
a=[]
a=list(map(int,sys.stdin.readline().rstrip().split()))
result=a[0]
prev_sum=a[0]
for i in range(1,n):
if prev_sum+a[i]>=a[i]:
prev_sum+=a[i]
else:
prev_sum=a[i]
result=max(prev_sum,result)
print(result)
처음 정답은 딥시크쨩 코드가 정답인지 확인해본거였다.
근데 결국 내 코드도 딥시크가 짜준 코드랑 동일하다...