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

 

2559번: 수열

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기

www.acmicpc.net

 

코드설명

누적합 문제입니다.

 

문제에서 유의해야할점은

1. PrefixSum = new int[N+1] 이기에 아래와 같이   i < N  - K +  1 까지 범위를 처리해야합니다.

for(int i=0;i<N - K + 1;i++) {
    int calculate = prefixSum[i + K] - prefixSum[i];
    answer = Math.max(answer, calculate);
}

2.온도값은 -100 이 최소수이고, N은 100000 이기에 100000 * 100 이 최소숫자입니다.

public static int answer = -100000 * 100;

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M, K, T;
	public static int answer = -100000 * 100;
	public static int[] arr;
	public static int[][] map;
	public static int[] prefixSum;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N];
    	prefixSum = new int[N+1];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    		prefixSum[i+1] = prefixSum[i] + arr[i];
    	}
    	
    	for(int i=0;i<N - K + 1;i++) {
    		int calculate = prefixSum[i + K] - prefixSum[i];
    		answer = Math.max(answer, calculate);
    	}
    	System.out.println(answer);
    	
	}
}

 

다른 형식으로 구현해본 누적합 코드입니다. 

prefixSum[i] = 0번째부터 i번쨰까지의 누적합을 저장한다.

import java.util.*;
import java.io.*;
 
public class Main {
    public static int N, K;
    public static long answer = Integer.MIN_VALUE;
    public static int[] arr;
    public static int[] prefixSum;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
 
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		arr = new int[N];
		prefixSum = new int[N];
		for(int i=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		for(int i=0; i<N; i++) {
			prefixSum[i] = ( i == 0 ? arr[i] : prefixSum[i - 1] + arr[i] );
		}
		for(int i=K - 1; i<N; i++) {
			answer = Math.max(answer, prefixSum[i] - (i == K - 1 ? 0 : prefixSum[i-K]));
		}
		System.out.println(answer);
	}
}

 

슬라이딩 윈도우를 활용할 경우입니다.

import java.util.*;
import java.io.*;
 
public class Main {
    public static int N, K;
    public static long answer = Integer.MIN_VALUE;
    public static int[] arr;
    public static int[] prefixSum;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
 
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		arr = new int[N];
		prefixSum = new int[N];
		for(int i=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int pSum = 0;
		for(int i=0; i<K-1; i++) {
			pSum += arr[i];
		}
		
		for(int i=K-1; i<N; i++) {
			pSum += arr[i];
			answer = Math.max(answer, pSum);
			pSum -= arr[i - K + 1];
		}
		
		System.out.println(answer);
	}
}

'알고리즘 > Prefix_Sum' 카테고리의 다른 글

[백준] 17390 이건 꼭 풀어야 해! - 누적합(PrefixSum) JAVA  (0) 2024.08.04
[백준] 2851 슈퍼 마리오 - 누적합(Prefix Sum) JAVA  (0) 2023.11.22
[백준] 16507 어두운 건 무서워 - 2차원 누적합(2차원 Prefix Sum) JAVA  (0) 2023.08.13
[백준] 11441 인간-컴퓨터 상호작용 - 누적합(Prefix Sum) + DP + 알파벳(문자열) JAVA  (0) 2023.08.13
[백준] 11441 합 구하기 - 누적합(Prefix Sum) JAVA  (0) 2023.08.13

+ Recent posts

티스토리툴바