https://www.acmicpc.net/problem/2003
2003번: 수들의 합 2
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
www.acmicpc.net
파이썬으로 비슷하게 코드를 짰었는데 시간초과가 나와서 오랜만에 C++로 풀어봤다.
이 코드는 시간복잡도가 O(n^2) 인데,
다른 풀이를 읽어보니까 투포인터 알고리즘으로 시간복잡도를 O(n)으로 줄일 수도 있었다..
28ms 에서 4ms로 시간이 확 줄어드는게 너무 신기하다!! ㅋㅋㅋㅋ
sum > m 이면 arr[start]를 빼고 start + 1
sum <= m 이면 arr[end]를 더하고 end + 1
참고
2003번 풀이: https://tooo1.tistory.com/143
'코딩테스트 > 백준' 카테고리의 다른 글
| [백준] 1644번: 소수의 연속합 (0) | 2023.09.25 |
|---|---|
| [백준] 1806번: 부분합 (0) | 2023.09.24 |
| [백준] 1182번: 부분수열의 합 (0) | 2023.09.23 |
| [백준] 1987번: 알파벳 (0) | 2023.09.22 |
| [백준] 6603번: 로또 (0) | 2023.09.21 |