acm 문제 낸 ㅇㅇ 봐라

[ㅁㄴㅇㄹ(166.147)]

걍 O(n) 에 풀리는 쉬운 문제잖아 ㅡㅡ

[익명(175.212)]

알고리즘 ㄱ

[ㅁㄴㅇㄹ(166.147)]

걍 2 sum 문제랑 비슷하게 인덱스 변수 두개로 풀림

[익명(175.212)]

구체적으로 말해봐

[ㅁㄴㅇㄹ(166.147)]

P[i] 를 i 번째 까지 부분 합이라고 정의했을때 i, j 를 0 으로 초기화. 반복문 돌리는데 매 반복문마다 i 를 증가시키고 j 는 P[i] - P[j + 1] >= S 가 성립 할때 까지 j 증가. i - j 가 가장 작은게 답

[ㅁㄴㅇㄹ(166.147)]

그런데 왜 자꾸 초딩 문제를 내냐 좀 대학생 수준으로 내줘라

[익명(175.212)]

그걸 정말로 O(n)이라고 생각하는 거임?

[ㅁㄴㅇㄹ(166.147)]

그럼 O(n) 이지 뭐겠냐 너 설마 시간 복잡도 계산도 못함?

[익명(175.212)]

계산은 니가 못하는것 같다...

[ㅁㄴㅇㄹ(166.147)]

딴것보다 구글에 2 sum 문제라고 검색이나 해봐라 거의 비슷한 문제

[익명(175.212)]

최악의 경우에 S이상인 경우가 안나오는데 그렇게 하면 1+2+3+...+n번 비교해보겠지? 그럼 그 횟수가 (n^2+n)/2다 그럼 O(n^2)이지 어떻게 O(n)이냐?

[ㅁㄴㅇㄹ(166.147)]

그리고 i 가 최대 n 번 증가 되고 j 가 최대 n 번 증가 되는데 O(n) 이지

[ㅁㄴㅇㄹ(166.147)]

잘봐 P[i] - P[j] >= S 라고 하자. 그럼 당연히 P[i + 1] - P[j] >= S 겠지? 그럼 굳이 1 ~ j - 1 은 필요가 없잖아?

[ㅁㄴㅇㄹ(166.147)]

설마 바이너리 서치같은 빠가 방법으로 풀지는 않았겠지?

[ㅁㄴㅇㄹ(166.147)]

이 새끼 또 버로우? ㅋㅋㅋㅋ