[BaekJoon] 2003 수들의 합 2

yunan·2020년 10월 2일
0
post-thumbnail

🔦 문제 링크

✍️ 나의 풀이


  • 투 포인터 문제
  • leftright를 정해서 값이 작으면 더해주고 크면 빼주고 같으면 count를 세주는 형식으로 진행한다.

투 포인터는 기준이 있고,
기준보다 작으면 현재 right인덱스에 해당하는 값을 더하고 right인덱스 증가.
기준보다 크면 left인덱스에 해당하는 값을 삭제하고 left인덱스 증가.

🛠 나의 코드


n, m = map(int, input().split())
arr = list(map(int, input().split()))
left = right = count = sm = 0
while left != n:
    if sm < m and right !=n:
        sm += arr[right]
        right += 1
    else:
        sm -= arr[left]
        left += 1
    if sm == m:
        count += 1

print(count)

✍️ 다른 사람 풀이


<중요포인트>

  • summ보다 더 작을 때 rightn을 넘어가면 sum이 더 증가할 수 없으므로 종료해도 상관없다.

🛠 다른 사람 코드


def solve():
    left = right = ans = s = 0
    while True:
        if s >= m:
            s -= a[left]
            left += 1
        else:
            if right == n:
                break
            s += a[right]
            right += 1
        if s == m:
            ans += 1
    return ans

📝 정리


  • 투 포인터 사용법에 대해 기억해두자.
  • O(n2)O(n^2) 걸리던 것을 O(2n)(?)O(2n)(?) 만에 해결 가능

🎈 참고


rebas님 블로그

profile
Go Go

0개의 댓글