๐ [๋ฐฑ์ค์๊ณ ๋ฆฌ์ฆ ํ์ด] Q.2559 ์์ด ๋ฌธ์ ํ์ด - java
๐ ๋ฌธ์
https://www.acmicpc.net/problem/2559
๐ ์ ๊ทผ๋ฒ
Q.2559 ์์ด ๋ฌธ์ ์ ๋๋ค.
์จ๋๊ฐ ์ด๋ค ์ ์์ ์์ด๋ก ์ฃผ์ด์ก์ ๋, ์ฐ์์ ์ธ ๋ฉฐ์น ๋์์ ์จ๋์ ํฉ์ด
๊ฐ์ฅ ํฐ ๊ฐ์ธ์ง๋ฅผ ์์๋ณด๋ ๋ฌธ์ ์ ๋๋ค.
์ ๋ ฅ์ผ๋ก ์ฐ์์ ์ธ ๋ ์ง๊ฐ k๋ก ๊ณ ์ ๋ฉ๋๋ค.
๊ทธ๋ฌ๋ฏ๋ก
์ฐ์ k์ผ ๋์์ ์จ๋์ ํฉ์ ๊ตฌํด์ฃผ๊ณ
์ฐ์์ ์ธ ๋ฉฐ์น ๋์์ ์จ๋์ ํฉ์ด๊ธฐ ๋๋ฌธ์
k์ผ ์ดํ๋ถํฐ๋
ํ์ฌ๊น์ง ํฉ์ ํฌํจ๋ ๊ฐ์ฅ ์ฒซ ๋ฒ์งธ ์จ๋๋ฅผ ๋นผ์ฃผ๊ณ ์๋ก์ด ๋ ์ง ์จ๋๋ฅผ ๋ํด์ฃผ๋ฉด
์ฐ์์ ์ธ k์ผ ๋์ ์จ๋์ ํฉ์ ๊ตฌํ ์ ์์ต๋๋ค.
ex) k๊ฐ 3์ธ ๊ฒฝ์ฐ 1,2,3 => 2,3,4 => 3,4,5 => 4,5,6
์ด๋ ๊ฒ ๊ตฌํด์ง k์ผ ๋์ ์จ๋์ ํฉ ์ค ๊ฐ์ฅ ํฐ ๊ฐ์ ๊ตฌํ๋ฉด
๋ต์ ๋์ถํ ์ ์์ต๋๋ค.
๐ป ์ฝ๋
package problem.twopointer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main_2559 {
static int n, k;
static int sequence[];
static int max = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
input();
solve();
System.out.println(max);
}
public static void solve(){
int sum = 0;
for(int i=0; i<k; i++){
sum += sequence[i];
}
max = Math.max(max,sum);
for(int i=k; i<n; i++){
sum -= sequence[i-k];
sum += sequence[i];
max = Math.max(max,sum);
}
}
public static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String temp[] = br.readLine().split( " ");
n = Integer.parseInt(temp[0]);
k = Integer.parseInt(temp[1]);
sequence = new int[n];
temp = br.readLine().split(" ");
for(int i=0; i<n; i++){
sequence[i] = Integer.parseInt(temp[i]);
}
}
}
Written on March 10, 2021