[백준/누적합] 11659: 구간 합 구하기 - 파이썬

2022. 5. 13. 21:41· Problem Solving/CT-Python
목차
  1. 문제
  2. 제출한 풀이

문제

https://www.acmicpc.net/problem/11659

 

11659번: 구간 합 구하기 4

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j

www.acmicpc.net

 

제출한 풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
num_list = list(map(int, input().split()))

sum_list = [0] * (n+1)
sum_list[1] = num_list[0]

for i in range(2, n+1):
    sum_list[i] = sum_list[i-1] + num_list[i-1]

for i in range(m):
    a, b = map(int, input().split())
    print(sum_list[b] - sum_list[a - 1])

 

누적합 알고리즘을 사용하여 푸는 문제

리스트 슬라이스를 이용해서 sum 연산을 하게 되면 시간복잡도가 O(N^2)이 되기 때문에 시간초과 발생한다.

누적합 알고리즘을 통해 시간복잡도를 O(N)까지 줄여서 풀어야 한다.

 

누적합 알고리즘의 원리는 여기에 정리해 두었다.

 

 

'Problem Solving > CT-Python' 카테고리의 다른 글

[백준/자료구조] 1620: 나는야 포켓몬 마스터 이다솜 - 파이썬  (0) 2022.05.13
[백준/구현] 2116: 주사위 쌓기 - 파이썬  (0) 2022.05.13
[백준/구현] 2304: 창고 다각형 - 파이썬  (0) 2022.05.13
[백준/DP] 2491: 수열 - 파이썬  (0) 2022.05.13
[SWEA/구현] 2007: 패턴 마디의 길이 - 파이썬  (0) 2022.05.04
  1. 문제
  2. 제출한 풀이
'Problem Solving/CT-Python' 카테고리의 다른 글
  • [백준/자료구조] 1620: 나는야 포켓몬 마스터 이다솜 - 파이썬
  • [백준/구현] 2116: 주사위 쌓기 - 파이썬
  • [백준/구현] 2304: 창고 다각형 - 파이썬
  • [백준/DP] 2491: 수열 - 파이썬
White Han
White Han
Software Developer
White Han
sudo apt-get happiness
White Han
전체
오늘
어제
  • 분류 전체보기 (183)
    • Language (35)
      • Java (17)
      • Java-Weekly-study (0)
      • Python (18)
    • BackEnd (11)
      • Server (2)
      • Spring (3)
      • Spring Security (0)
      • JDBC (1)
      • NodeJS (2)
      • LINUX (3)
    • DataBase (10)
      • MySQL (5)
      • MongoDB (4)
      • Oracle (1)
    • Infra (4)
      • Docker (4)
    • CS (38)
      • OS (38)
    • Problem Solving (79)
      • Algorithm (8)
      • CT-Java (30)
      • CT-Python (41)
    • IDE (1)
      • eclipse (1)
      • vscode (0)
    • Etc. (3)
      • Git (1)
      • TDD, Refactor, CleanCode (1)
      • Conference (1)
    • 기록 (2)
      • 후기 (1)
      • 프로젝트 회고록 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기

공지사항

  • 방문해 주셔서 감사합니다.

인기 글

태그

  • 자바스크립스 식별자 종류
  • 싸피 후기
  • 자바스크립트
  • 운영체제
  • 프로세스
  • Java super
  • 자바스크립트 식별자
  • 운영체제 구조
  • 알파스캔 AOC 24B1X
  • 알파스캔 모니터
  • Java this
  • 24인치 모니터 추천
  • 싸피 합격
  • 사무용 모니터
  • 자바 inheritance
  • javascript identifier
  • Java Inheritance
  • 프로세서
  • javascript
  • AOC 24B1X
  • java
  • SSAFY
  • 자바 super
  • 자바 this
  • 사무용 모니터 추천
  • 싸피8기
  • OS
  • 싸피
  • 운영체제 역할
  • 자바스크립트 개념

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
White Han
[백준/누적합] 11659: 구간 합 구하기 - 파이썬
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.