๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/11659
- ์ N๊ฐ๊ฐ ์ฃผ์ด์ก์ ๋, i๋ฒ์งธ ์๋ถํฐ j๋ฒ์งธ ์๊น์ง ํฉ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ์ฒซ์งธ ์ค์ ์์ ๊ฐ์ N๊ณผ ํฉ์ ๊ตฌํด์ผ ํ๋ ํ์ M์ด ์ฃผ์ด์ง๋ค.
- ๋์งธ ์ค์๋ N๊ฐ์ ์๊ฐ ์ฃผ์ด์ง๋ค. ์๋ 1,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค.
- ์ ์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์๋ ํฉ์ ๊ตฌํด์ผ ํ๋ ๊ตฌ๊ฐ i์ j๊ฐ ์ฃผ์ด์ง๋ค.
- ์ด M๊ฐ์ ์ค์ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง i๋ฒ์งธ ์๋ถํฐ j๋ฒ์งธ ์๊น์ง ํฉ์ ์ถ๋ ฅํ๋ค.
์์ด๋์ด
- ์ฒ์์๋ ๋ฐ๋ณต๋ฌธ์ ๋๋ ค์ ์ผ์ผ์ด ๋ํ๋ฉด ์ฝ๊ฒ ๋ค๊ณ ์๊ฐํ์ง๋ง ๊ทธ๋ ๊ฒ ํ ๊ฒฝ์ฐ, ์๊ฐ์ด๊ณผ๊ฐ ๋ ๊ฒ ๊ฐ๋ค๋ ์๊ฐ์ด ๋ค์๋ค.
- ๊ทธ๋์ ๊ตฌ๊ฐํฉ์ ์ ์ฅํ N + 1 ํฌ๊ธฐ์ ๋ฐฐ์ด์ ๋ง๋ค์ด์ค๋ค.
- ์ซ์๋ค์ ์ ๋ ฅ๋ฐ์ผ๋ฉด์ ์ฐจ๋ก๋๋ก ๋ํด์ฃผ๊ณ ๋ํ ๊ฐ์ ํด๋น ๋ฐฐ์ด์ ์๋ฒ์ ์ ์ฅํ๋ค.
- ์๋ฅผ ๋ค์ด, ์ฒซ๋ฒ์งธ ๊ฐ์ 1 ์ ๋ ฅ๋ฐ์ผ๋ฉด ๋ํ๋๋ฐ ์ฐ๊ธฐ์ํด ์ ์ธํด ๋์ ๋ณ์์ 1์ ๋ํ๊ณ ๋ฐฐ์ด ์ฒซ๋ฒ์งธ ๊ฐ์ 1์ ๋ฃ๋๋ค.
- ๋๋ฒ์งธ๋ก ๋์ด๊ฐ์ 3์ ์ ๋ ฅ๋ฐ์ผ๋ฉด ์์์ ์ผ๋ ๋ณ์ ๊ฐ 1์ 3์ ๋ํด์ ๋ฐฐ์ด ๋๋ฒ์งธ ๊ฐ์ 4๋ฅผ ๋ฃ๋๋ค.
- ์ด๋ฐ์์ผ๋ก ํ๋์ ๋ณ์์ ์ฐจ๋ก๋๋ก ์ ๋ ฅ๋ฐ์ ๊ฐ์ ๋ํด์ฃผ๊ณ ๋ฐฐ์ด์ ์์๋๋ก ์ ์ฅํ๋ค.
- ๊ทธ๋ฆฌ๊ณ ๊ตฌํ ๊ตฌ๊ฐํฉ์ ๋์ ์ ํด๋นํ๋ ๋ฐฐ์ด ๊ฐ์์ ์์์ ๋ณด๋ค 1 ์์ ๋ฐฐ์ด ๊ฐ์ ๋นผ๋ฉด ๊ตฌ๊ฐํฉ์ด ๋๋ค.
- ์ฒ์๋ถํฐ ์ด๋์ง์ ๊น์ง ๊ตฌ๊ฐํฉ์ ๊ตฌํ๋ ๊ฒฝ์ฐ, ๋ง์ฝ ๋ฐฐ์ด์ด 0๋ถํฐ ์์ํ๋ฉด ๋ฐฐ์ด ๋ฒ์ ์ค๋ฅ๊ฐ ๋๋ฏ๋ก ๋ฐฐ์ด ๊ฐ์ index 1๋ถํฐ ์ ์ฅํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- X
์ฝ๋
import java.util.*;
import java.io.*;
public class BOJ11659 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
// ์์ ๊ฐ์
int N = Integer.parseInt(st.nextToken());
// ํฉ์ ๊ตฌํด์ผ ํ๋ ๊ตฌ๊ฐ ์
int M = Integer.parseInt(st.nextToken());
// ๊ตฌ๊ฐ์ ํฉ์ ์ ์ฅํ ๋ฐฐ์ด
int sum[] = new int[N + 1];
StringTokenizer st2 = new StringTokenizer(br.readLine());
// ๊ตฌ๊ฐ๋ค์ ํฉ์ ๊ตฌํ ๋ณ์
int s = 0;
for(int i = 1; i <= N; i++){
int n = Integer.parseInt(st2.nextToken());
// ๊ตฌ๊ฐํฉ์ ๊ตฌํ๊ธฐ ์ํด์ i๋ฒ์งธ ๋ฐฐ์ด์
// i๋ฒ์งธ๊น์ง ์ซ์๋ค์ ํฉ์ ์ ์ฅ
s = s + n;
sum[i] = s;
}
// ๊ตฌ๊ฐํฉ์ ๊ฐ์๋งํผ ๋ฐ๋ณต
for(int i = 0; i < M; i++){
StringTokenizer st3 = new StringTokenizer(br.readLine());
// ์์์
int start = Integer.parseInt(st3.nextToken());
// ๋์
int end = Integer.parseInt(st3.nextToken());
// ๊ตฌ๊ฐ์ ํฉ์ ๋์ ๊น์ง ๋ํ ๊ฐ๊ณผ ์์์ ์ ๊น์ง ๋ํ ๊ฐ์
// ๋นผ๋ ๊ฒ๊ณผ ๊ฐ์ผ๋ฏ๋ก sum[end] - sum[start - 1]์ ์ถ๋ ฅ
sb.append(sum[end] - sum[start - 1] + "\n");
}
System.out.println(sb);
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 11727 2รn ํ์ผ๋ง 2 (0) | 2024.07.30 |
---|---|
[Java] BOJ 11726 2รn ํ์ผ๋ง (0) | 2024.07.29 |
[Java] BOJ 9461 ํ๋๋ฐ ์์ด (0) | 2024.07.28 |
[Java] BOJ 9375 ํจ์ ์ ์ ํด๋น (0) | 2024.07.28 |
[Java] BOJ 9095 1, 2, 3 ๋ํ๊ธฐ (0) | 2024.07.28 |