방명록
- [백준 / 자바] 11659번 구간 합 구하기 4 - 구간 합2023년 12월 18일 22시 48분 45초에 업로드 된 글입니다.작성자: 민발자728x90
문제
수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
5 3 5 4 3 2 1 1 3 2 4 5 5
출력
총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.
12 9 1
제한
- 1 ≤ N ≤ 100,000
- 1 ≤ M ≤ 100,000
- 1 ≤ i ≤ j ≤ N
풀이
수의 개수(N)와 합을 구해야 하는 횟수(M)는 최대 100,000
구간마다 합을 매번 계산하면 제한 시간 내에 풀 수 없다.
→ 구간 합을 매번 계산하게 되면 최악의 경우 1억 회 이상 연산 수행이 필요, 1초 이상의 시간이 필요(대략 1억 회에 1초 정도로 생각)
합 배열을 사용하여 계산
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); // 숫자 개수 int m = Integer.parseInt(st.nextToken()); // 합 횟수 // 합배열 만들기 long[] s = new long[n+1]; st = new StringTokenizer(br.readLine()); for(int i = 1; i <= n; i++){ s[i] = s[i-1] + Integer.parseInt(st.nextToken()); } // m만큼 반복 for(int k = 0; k < m; k++) { st = new StringTokenizer(br.readLine()); int i = Integer.parseInt(st.nextToken()); int j = Integer.parseInt(st.nextToken()); // 구간합 출력 System.out.println(s[j] - s[i-1]); }
728x90'기록 > 백준' 카테고리의 다른 글
[백준 / 자바] 1874번 스택 수열 - 스택 (0) 2023.12.19 [백준 / 자바] 2018번 수들의 합 5 - 투 포인터 (2) 2023.12.19 [백준 / 자바] 24267번 알고리즘 수업 - 알고리즘의 수행 시간6 (0) 2023.12.18 [백준 / 자바] 24266번 알고리즘 수업 - 알고리즘의 수행 시간5 (0) 2023.12.17 [백준 / 자바] 1546번 평균 (0) 2023.12.16 다음글이 없습니다.이전글이 없습니다.댓글