[Algorithm] 백준_특정한 최단 경로_1504번 (JAVA) 투포인터 알고리즘

📝문제

https://www.acmicpc.net/problem/2559

티어: 실버3

💡풀이

문제 유형

투포인터 알고리즘

 

걸린 시간

20분

 

시간 복잡도

 

 

풀이 방법 도출

1. 연속적이고, 범위가 계속 오른쪽으로 이동하는 문제여서 투포인터를 바로 떠올릴 수 있었다.
2. left = 0, right = K 로두고 right가 N이하일때 까지 반복하는 반복문을 작성한다.
3. 이때 결과값인 max는 int범위의 최소값으로 설정해야 한다. 입력 받는 정수의 범위가 -100 ~ 100이기 때문에!
4. 이후 left부터 right까지의 arr의 합을 구해 max와 비교해주면 답을 도출할 수 있다.

import java.util.*;
import java.io.*;
class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int left = 0;
        int right = K;
        int sum = 0;
        int max = Integer.MIN_VALUE;
        while(right<= N){
            sum = 0;
            for(int i = left; i < right; i++){
                sum += arr[i];
            }
            max = Math.max(max, sum);
            left++;
            right = left+K;
        }

        System.out.println(max);
    }
}

 

🤔Review

다음주 일요일 코테본다 화이팅ㅇㅇㅇㅇ