๐ [๋ฐฑ์ค์๊ณ ๋ฆฌ์ฆ ํ์ด] Q.2003 ์๋ค์ ํฉ 2 ํ์ด ํฌ ํฌ์ธํฐ ๋ฐฉ์ - java
๐ ๋ฌธ์
https://www.acmicpc.net/problem/2003
N๊ฐ์ ์๋ก ๋ ์์ด A[1], A[2], โฆ, A[N] ์ด ์๋ค. ์ด ์์ด์ i๋ฒ์งธ ์๋ถํฐ j๋ฒ์งธ ์๊น์ง์
ํฉ A[i] + A[i+1] + โฆ + A[j-1] + A[j]๊ฐ M์ด ๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๐ ์ ๊ทผ๋ฒ
Q.2003 ์๋ค์ ํฉ 2 ๋ฌธ์ ์ ๋๋ค.
i๋ฒ์งธ ์๋ถํฐ j๋ฒ์งธ ์๊น์ง์ ์ฐ์ ๋ ํฉ์ด M์ด ๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ ๋๋ค.
์ฌ๊ธฐ์ i๋ฒ์งธ ์๋ถํฐ j๋ฒ์งธ ์๊น์ง ์ฐ์ ๋ ํฉ์ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ฏ๋ก
๋์ ํฉ์ ์ด์ฉํด์ ์ฝ๊ฒ ํ์ด๊ฐ ๊ฐ๋ฅํ์ต๋๋ค.
๋์ ํฉ์ ๊ตฌํ๋๋ฐ ๊น์ง๋ O(N) ์๊ฐ๋ง์ ๊ฐ๋ฅํ์ง๋ง
์ด ๋์ ํฉ์ ์ด์ฉํด ๊ฐ๊ฐ์ i๋ฒ์งธ๋ถํฐ j๋ฒ์งธ๊น์ง์ ํฉ์ ๊ตฌํ๋ ๋ฐ๋
์ด์ค for๋ฌธ์ผ๋ก O(N^2)์ ์๊ฐ์ด ๊ฑธ๋ฆฌ๊ฒ ๋ฉ๋๋ค.
์ด๋ฅผ ์ข ๋ ํจ์จ์ ์ผ๋ก ํ์ดํ ์ ์๋ ๋ฐฉ๋ฒ์ด ์์ต๋๋ค.
๋ฐ๋ก two pointer ๋ฐฉ์์ ๋๋ค.
ํฌ ํฌ์ธํฐ ๋ฐฉ์์ ์ด๋ฆ ๊ทธ๋๋ก ๋๊ฐ์ ํฌ์ธํฐ๋ฅผ ๊ฐ์ง๊ณ
์์์ ๊ณผ ๋์ ์ผ๋ก ๋ฌ์ ํ์ดํ๋ ๋ฐฉ์์ ๋งํฉ๋๋ค.
์ด ํฌ ํฌ์ธํฐ ๋ฐฉ์์ ์ด์ฉํ๋ฉด
o(N) ์๊ฐ๋ง์ ๋ต์ ์ฝ๊ฒ ๊ตฌํ ์ ์์ต๋๋ค.
Q.2003 ์๋ค์ ํฉ 2 ๋ฌธ์ ๊ฐ์ ๊ฒฝ์ฐ์๋
๋ชจ๋ ์์ฐ์๋ก ์ด๋ฃจ์ด์ ธ์๊ธฐ ๋๋ฌธ์!
m๋ณด๋ค ํฉ์ด ์๋ค๋ฉด end๋ฅผ (๋ ์ง์ ) ํ๋์ฉ ๋๋ ค์ฃผ๋ฉฐ ์๋ฅผ ๋ ํด์ฃผ๋ฉด ๋๊ณ
๋ฐ๋๋ก m๋ณด๋ค ํฉ์ด ์ปค์ง๋ค๋ฉด start๋ฅผ (์ ์ง์ ) ํ๋์ฉ ๋๋ ค์ฃผ๋ฉฐ ์ ์ง์ ์ ์๋ฅผ ๋นผ์ฃผ๋ฉด
์ฝ๊ณ ๋น ๋ฅด๊ฒ i (start) ๋ถํฐ j (end) ๊น์ง์ ํฉ์ด ๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ
๊ตฌํ ์ ์์ต๋๋ค.
๐ป ์ฝ๋
package problem.twopointer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main_2003 {
static int n,m;
static int numbers[];
static int count = 0;
public static void main(String[] args) throws IOException {
input();
solve();
System.out.println(count);
}
public static void solve(){
int p1,p2;
int sum = 0;
p1 = 0;
p2 = 0;
while (true){
if(sum >= m){
sum -= numbers[p1++];
}
else if(p2 == n){
break;
}
else {
sum+= numbers[p2++];
}
if(sum == m){
count++;
}
}
}
public static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String temp[] = br.readLine().split( " ");
n = Integer.parseInt(temp[0]);
m = Integer.parseInt(temp[1]);
numbers = new int[n];
temp = br.readLine().split(" ");
for(int i=0; i<n; i++){
numbers[i] = Integer.parseInt(temp[i]);
}
}
}