[๋ฐฑ์ค ๋์ ํฉ] 11659๋ฒ: ๊ตฌ๊ฐ ํฉ ๊ตฌํ๊ธฐ 4
https://www.acmicpc.net/problem/11659
11659๋ฒ: ๊ตฌ๊ฐ ํฉ ๊ตฌํ๊ธฐ 4
์ฒซ์งธ ์ค์ ์์ ๊ฐ์ N๊ณผ ํฉ์ ๊ตฌํด์ผ ํ๋ ํ์ M์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ N๊ฐ์ ์๊ฐ ์ฃผ์ด์ง๋ค. ์๋ 1,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ์ ์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์๋ ํฉ์ ๊ตฌํด์ผ ํ๋ ๊ตฌ๊ฐ i์ j
www.acmicpc.net
๊ตฌ๊ฐ ํฉ ๊ตฌํ๊ธฐ 4 ์ฑ๊ณต
1 ์ด | 256 MB | 101082 | 41558 | 30954 | 39.014% |
๋ฌธ์
์ N๊ฐ๊ฐ ์ฃผ์ด์ก์ ๋, i๋ฒ์งธ ์๋ถํฐ j๋ฒ์งธ ์๊น์ง ํฉ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์์ ๊ฐ์ N๊ณผ ํฉ์ ๊ตฌํด์ผ ํ๋ ํ์ M์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ N๊ฐ์ ์๊ฐ ์ฃผ์ด์ง๋ค. ์๋ 1,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ์ ์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์๋ ํฉ์ ๊ตฌํด์ผ ํ๋ ๊ตฌ๊ฐ i์ j๊ฐ ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ด M๊ฐ์ ์ค์ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง i๋ฒ์งธ ์๋ถํฐ j๋ฒ์งธ ์๊น์ง ํฉ์ ์ถ๋ ฅํ๋ค.
์ ํ
- 1 ≤ N ≤ 100,000
- 1 ≤ M ≤ 100,000
- 1 ≤ i ≤ j ≤ N
์์ ์ ๋ ฅ 1 ๋ณต์ฌ
5 3
5 4 3 2 1
1 3
2 4
5 5
์์ ์ถ๋ ฅ 1 ๋ณต์ฌ
12
9
1
<<ํ์ด>>
-๋์ ํ์ด-
ํ ์ผ๋จ ํด๋์ค๋ก ๋ฐ๋ก ๋ง๋ค๊ณ ๊ฐ์ฒด ์ด์ฉํด์ ํ์์ง๋ง ์๊ฐ์ด๊ณผ์ด๋ค.
import java.util.*;
class Sum {
int first;
int last;
Sum(int first, int last) {
this.first = first;
this.last = last;
}
}
class Main {
private int[] solution(int[] arr, Sum[] brr) {
int sum = 0;
int[] answer = new int[brr.length];
for(int i = 0; i < brr.length; i++){
for(int j = brr[i].first; j <= brr[i].last; j++) {
sum += arr[j - 1];
}
answer[i] = sum;
sum = 0;
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}
Sum[] brr = new Sum[m];
for(int i = 0; i < m; i++) {
brr[i] = new Sum(in.nextInt(), in.nextInt());
}
for(int x : T.solution(arr, brr)){
System.out.println(x);
}
}
}
-์์ ํ ์ฝ๋-
์์ธ์ ์ฐพ์ ์ ์์๋๋ฐ ์ด์ค for๋ฌธ์ ๋๊ณ ์๋ ๋ถ๋ถ์์ ๋ฌธ์ ์๋ ๊ฒ์ด๋ค. ๋๋ฆ ์ง์์ ํ์ง๋ง, ์ฐ๋ฆฌ๋ ์ด๋
"๋์ ํฉ"์ ์ด์ฉํ๋๋ฐ, ์ด๋ฅผ ํ์ฉํ๋ฉด ์ด์ค for๋ฌธ์ ์ฌ์ฉํ์ง ์๊ณ ์ฝ๋๋ฅผ ์งค ์ ์๊ณ , ์๊ฐ์ด๊ณผ์์ ๋ฒ์ด๋ ์ ์๋ค.
import java.util.*;
class Sum {
int first;
int last;
Sum(int first, int last) {
this.first = first;
this.last = last;
}
}
class Main {
private int[] solution(int[] arr, Sum[] brr) {
int[] prefixSum = new int[arr.length + 1];
for (int i = 1; i <= arr.length; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
}
int[] answer = new int[brr.length];
for (int i = 0; i < brr.length; i++) {
answer[i] = prefixSum[brr[i].last] -
prefixSum[brr[i].first - 1];
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}
Sum[] brr = new Sum[m];
for(int i = 0; i < m; i++) {
brr[i] = new Sum(in.nextInt(), in.nextInt());
}
for(int x : T.solution(arr, brr)){
System.out.println(x);
}
}
}
๋์ ํฉ์ด๋
๋ฐฐ์ด์ ์๋ ๊ฒ์ ์ฒ์ ๋ถํฐ ๋์ ํ ๊ฒ๋ค์ ์๋ก์ด ๋ฐฐ์ด prefix๋ผ๋ ๊ณณ์ ๋ฃ์ด๋๋ค. ๊ทธ๋ฆฌ๊ณ ๋ง์ฝ 3๋ฒ์งธ์์ 5๋ฒ์งธ์ ๋์ ํฉ์ ์๊ณ ์ถ์ผ๋ฉด,
23 - 9๋ฅผ ํ๋ฉด ์ฝ๊ฒ ๊ตฌํ ์ ์๋ค.
์ด๋ฅผ ํ์ฉํจ์ผ๋ก์จ ์ด์ค for๋ฌธ์ผ๋ก ์๊ฐ๋ณต์ก๋๊ฐ O(N^2) ์ด ๋ ์ ์๋ ๊ฒ์ ๋จ์ํ ์ฌ์น์ฐ์ฐ ๋นผ๊ธฐ๋ก ๊ตฌํ ์ ์๊ฒ ๋จ์ผ๋ก์จ ์๊ฐ๋ณต์ก๋๋ฅผ O(N)์ผ๋ก ๋ง๋ค ์ ์๋ค.
๋์ ํฉ ์ง์ด๋ค ~~๐
'์ฝ๋ฉํ ์คํธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์ธํ๋ฐ_๋ฒ๋ธ ์ ๋ ฌ] 2. ๋ฒ๋ธ ์ ๋ ฌ (1) | 2024.01.15 |
---|---|
[์ธํ๋ฐ_์ ํ ์ ๋ ฌ] 1. ์ ํ ์ ๋ ฌ (0) | 2024.01.15 |
[ํ] 8. ์๊ธ์ค (1) | 2024.01.14 |
[ํ] 7. ๊ต์ก๊ณผ์ ์ค๊ณ (1) | 2024.01.13 |
[ํ] 6. ๊ณต์ฃผ ๊ตฌํ๊ธฐ (1) | 2024.01.13 |
๋๊ธ