[백준/Java, Kotlin] 1806번 부분합

 

 

문제 풀이(Java만 설명)

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

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

int[] arr = new int[N];

int min = Integer.MAX_VALUE;

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

1. 주어진 입력을 받고 배열을 초기화한다.

 

int pfSum[] = new int[N+2];
for(int i=1; i<=N; i++) {
    pfSum[i] = pfSum[i-1] + arr[i-1];
}

2. 누적합을 저장할 정수 배열(pfSum)을 만든다.

이 때, 배열의 크기는 N+2로 한다.

누적합 공식은 pfSum[i] = pfSum[i-1] + arr[i-1] 이다.

 

int start = 1;
int end = 1;

int sum = pfSum[start];

while(start <= end && end <= N) {
    if(sum >= M) {
        min = Math.min(min, end-start+1);
        start++;
    }else {
        end++;
    }
    sum = pfSum[end] - pfSum[start-1];

}

3. 두 개의 포인터의 위치를 각각 1로 한다.

이 때, 두 포인터 사이의 합은 pfSum[start]이다. 왜냐하면 두 포인터의 위치가 같기 때문 !

while문을 반복하며,

만약 sum >= M인 경우,

현재 구간의 합이 목표 값(M) 이상이므로 min을 갱신하고, start를 오른쪽으로 이동시킨다.

sum < M 인 경우,

end를 오른쪽으로 이동하여 구간의 크기를 늘린다.

 

if(min == Integer.MAX_VALUE) {
    System.out.println(0);
}else {
    System.out.print(min);
}

4. 출력할 때 주의할 점이 있다.

10 11

1 1 1 1 1 1 1 1 1 1

과 같은 입력이 주어진다면 0이 출력되어야하지만 만족하는 구간이 없기 때문에 Integer.MAX_VALUE가 출력된다.

그렇기 때문에 min의 값이 Integer.MAX_VALUE라면 0을 출력하고 그렇지 않다면 min을 출력한다.

 

 

오랜만에 골드 문제를 다른 사람 풀이 없이 스스로 풀었더니 너무 뿌듯하다.

이번 주 알고리즘 스터디에 누가 투 포인터 문제를 내서 풀었는데 아직 투 포인터에 대해 무지한 것 같아서 관련 문제들을 많이 풀어봤다.

어느 정도 풀 수 있겠다고 생각했지만 문제의 유형이 너무 다양해서 더 많은 문제들을 접해봐야겠다. ㅠ ㅎ

 

코드

• Java 풀이

package baekjoon0822;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class 부분합_1806 {
	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 M = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[N];
		
		int min = Integer.MAX_VALUE;
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int pfSum[] = new int[N+2];
		for(int i=1; i<=N; i++) {
			pfSum[i] = pfSum[i-1] + arr[i-1];
		}
		
		int start = 1;
		int end = 1;
		
		int sum = pfSum[start];
		
		while(start <= end && end <= N) {
			if(sum >= M) {
				min = Math.min(min, end-start+1);
				start++;
			}else {
				end++;
			}
			sum = pfSum[end] - pfSum[start-1];
			
		}
		
		if(min == Integer.MAX_VALUE) {
			System.out.println(0);
		}else {
			System.out.print(min);
		}
	}
}

 

• Kotlin 풀이

fun main(){
    var (N, S) = readln().split(" ").map{ it.toInt() }
    var arr = readln().split(" ").toTypedArray().map{ it.toInt() }
    var pfNum = MutableList(N+2){ 0 }
    var min = Integer.MAX_VALUE


    for(n in 1 ..N){
        pfNum[n] = pfNum[n-1] + arr[n-1]
    }

    var start = 1
    var end = 1

    var sum = pfNum[start]

    while(start <= end && end <= N){

        if(sum >= S){
            min = minOf(min, end-start+1)
            start++
        }else{
            end++
        }
        sum = pfNum[end] - pfNum[start-1]
    }

    if(min == Integer.MAX_VALUE){
        println(0)
    }else{
        println(min)
    }
}

 

 

 

 

 

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