๐ [๋ฐฑ์ค์๊ณ ๋ฆฌ์ฆ ํ์ด] Q.1806 ๋ถ๋ถํฉ ๋ฌธ์ ํ์ด - java
๐ ๋ฌธ์
https://www.acmicpc.net/problem/1806
10,000 ์ดํ์ ์์ฐ์๋ก ์ด๋ฃจ์ด์ง ๊ธธ์ด N์ง๋ฆฌ ์์ด์ด ์ฃผ์ด์ง๋ค.
์ด ์์ด์์ ์ฐ์๋ ์๋ค์ ๋ถ๋ถํฉ ์ค์ ๊ทธ ํฉ์ด S ์ด์์ด ๋๋ ๊ฒ ์ค, ๊ฐ์ฅ ์งง์ ๊ฒ์ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๐ ์ ๊ทผ๋ฒ
Q.1806 ๋ถ๋ถํฉ ๋ฌธ์ ์ ๋๋ค.
๊ธธ์ด๊ฐ N์ง๋ฆฌ์ธ ์์ด์ด ์ฃผ์ด์ง๋๋ฐ ์ด ์ฃผ์ด์ง ์์ด์์ ์ฐ์๋ ์๋ค์ ๋ถ๋ถํฉ ์ค์
ํฉ์ด S์ด์์ด ๋๋ ๊ฒ๋ค ์ค ๊ฐ์ฅ ์งง์ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ ๋๋ค.
ํฌ ํฌ์ธํฐ๋ฅผ ์ด์ฉํ์ฌ ํ์ด๊ฐ ๊ฐ๋ฅํฉ๋๋ค.
๋ชจ๋ ์์ฐ์๋ก ์ด๋ค์ ธ์์ผ๋ฏ๋ก!
S๋ณด๋ค ํฉ์ด ์๋ค๋ฉด end๋ฅผ (๋์ชฝ ํฌ์ธํฐ) ํ๋์ฉ ๋๋ ค์ฃผ๋ฉฐ ์๋ฅผ ๋ ํด์ฃผ๋ฉด ๋๊ณ
๋ฐ๋๋ก S๋ณด๋ค ํฉ์ด ์ปค์ง๋ค๋ฉด start๋ฅผ (์์ชฝ ํฌ์ธํฐ) ํ๋์ฉ ๋๋ ค์ฃผ๋ฉฐ ์ ์ง์ ์ ์๋ฅผ ๋นผ์ฃผ๋ฉด
์ฝ๊ฒ ํฉ์ด S์ด์์ด ๋๋ ๊ฒฝ์ฐ๋ค์ ์ฐพ์ ์ ์์ต๋๋ค.
๊ทธ ์ค์์ ๊ธธ์ด๊ฐ ๊ฐ์ฅ ์งง์ ๊ฒฝ์ฐ๋ฅผ ๊ตฌํ๋ฉด ๋ต์ ๊ตฌํ ์ ์์ต๋๋ค.
๐ป ์ฝ๋
package problem.twopointer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main_1806 {
static int n, m;
static int numbers[];
static int start, end;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
input();
solve();
if (min == Integer.MAX_VALUE)
System.out.println(0);
else
System.out.println(min);
}
private static void solve() {
int sum = 0;
start = 0;
end = 0;
while (true) {
if (sum >= m) {
sum -= numbers[start++];
} else if (end == n) {
break;
} else {
sum += numbers[end++];
}
if (sum >= m) {
min = Math.min(min, end - start);
}
}
}
private 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]);
}
}
}