백준 30646번: 최대 합 순서쌍의 개수

문제: https://www.acmicpc.net/problem/30646

문제 풀이

누적합

sum[i] = 1번 원소부터 i번 원소까지의 누적합

map[a] = a가 배열에서 존재하는 시작 위치와 마지막 위치를 배열 형태로 저장

answer = 순서쌍의 합의 최댓값

count = 최댓값을 가지는 순서쌍의 개수

원소가 양의 정수이고 순서쌍의 합이 같은 값을 가지는 두 원소를 포함해 사이에 있는 모든 원소의 합이므로 원소마다 구간이 길수록 합이 커짐

따라서 원소마다 시작 위치, 마지막 위치를 알면 그 원소의 순서쌍의 합의 최댓값을 구할 수 있음

그리고 순서쌍의 합을 매번 구하기는 너무 오래 걸리므로 누적합을 이용해 구하면 빠르게 구할 수 있음

따라서 원소를 입력받으며 1번 원소부터 i번 원소까지의 누적합을 sum[i]에 저장함

이때 누적합은 원소 하나가 $10^9$이므로 Long의 범위여야 함

그리고 원소를 입력받을 때 원소 a에 대해 map[a]가 존재하지 않는다면 해당 원소가 처음 나온 것이므로 map[a]에 해당 위치 i를 시작 위치, 마지막 위치로 하는 배열을 저장함

만약 존재한다면 a가 나오는 마지막 위치가 현재 위치 i로 갱신되는 것이므로 map[a][1]에 i를 저장함

모든 원소에 대해 arr, map에 값을 채운 이후에는 순서쌍 합의 최댓값과 최댓값이 되는 순서쌍의 개수를 구해야 하므로 각각 answer, count 변수를 정의하고 answer는 마찬가지로 합이므로 Long으로 정의함

map에 존재하는 배열이 원소가 존재하는 시작 위치와 마지막 위치가 저장된 배열이므로 모든 배열 arr에 대해 해당 순서쌍의 합을 curSum에 구해서 저장함

curSum과 answer를 비교해 curSum이 더 크다면 지금까지 찾은 순서쌍 합의 최댓값보다 더 큰 값을 찾은 것이므로 answer를 curSum으로 갱신하고 count를 1로 갱신함

만약 curSum이 answer와 같다면 최댓값을 가지는 순서쌍을 새로 찾은 것이므로 count만 1 증가시킴

모든 배열에 대해 처리하면 찾는 값이 answer, count에 저장되므로 이를 출력해주면 정답

풀이 설명

크기가 N인 배열 a가 주어진다. 배열 a의 임의의 위치를 나타내는 두 수 i, j를 골랐을 때, 아래 두 조건을 만족하면 같은 수 순서쌍 (i, j)를 만들 수 있다.

• 1 ≤ i ≤ j ≤ N
• $a_i = a_j$

만들어진 같은 수 순서쌍 (i, j)의 합은 $a_i$부터 $a_j$까지의 합 $a_i + a_{i+1} + a_{i+2} + … + a_{j-1} + a_j$로 정의된다. 이때 주어진 배열에서 만들 수 있는 같은 수 순서쌍의 최대 합을 찾고, 최대 합을 가지는 같은 수 순서쌍의 개수를 출력하는 프로그램을 작성하시오.

배열의 원소가 양의 정수이고, 같은 수 순서쌍의 최대 합을 찾는 문제이므로 같은 수 순서쌍의 길이가 길 수록 합이 커지게 된다. 따라서 수마다 처음 나온 위치와 마지막으로 나온 위치를 찾아놓으면 이 두 위치로 만드는 순서쌍의 길이가 가장 길어지므로 이 순서쌍의 합이 그 수로 만드는 순서쌍의 최대 합이 된다.

따라서 배열에 존재하는 수마다 처음 나온 위치, 마지막으로 나온 위치를 저장해야 하는데 이를 단순히 배열에 저장하기엔 원소가 최대 $10^9$이므로 메모리를 너무 많이 잡아먹게 된다.

그러므로 배열의 수를 Key, 수가 나온 처음, 마지막의 위치를 배열에 저장해 Value로 사용하는 맵을 사용하면 배열에 존재하는 원소들에 대해서만 배열을 저장하는 것이므로 메모리를 더 효율적으로 사용할 수 있게 된다.

그리고 이렇게 같은 원소를 시작과 끝으로 하는 가장 긴 순서쌍을 찾고 나서는 순서쌍의 합을 구해야 하는데 순서쌍의 합의 정의에 따라 시작 원소부터 끝 원소까지의 합으로 나타나므로 매번 원소들을 직접 더하는 것이 아닌 누적합을 배열에 저장해놓고 사용하는 것이 더 빠르게 계산을 할 수 있다.

이에 따라 1번 원소부터 i번째 원소까지의 누적합을 sum[i]에 저장을 하고, 배열의 원소 a에 대해 map[a]에 원소 a가 처음 등장하는 위치와 마지막 위치를 배열의 형태로 저장을 한다.

그 이후 맵에 저장된 모든 배열 arr에 대해 arr[0]이 해당 원소가 처음 등장하는 위치, arr[1]이 해당 원소가 마지막으로 등장하는 위치이므로 해당 원소의 가장 긴 순서쌍의 합이 sum[arr[1]] - sum[arr[0] - 1]으로 구할 수 있으므로 이 값을 curSum에 저장하고 최댓값을 저장한 answer와 비교해 더 크다면 answer를 curSum에 저장된 값을 저장한다.

그리고 순서쌍의 개수도 저장을 해야 하므로 answer에 새로운 값을 저장할때마다 count를 1로 초기화하고 만약 answer와 curSum이 같다면 최대값인 순서쌍을 더 찾은 것이므로 count만 1씩 증가시키면 된다.

이에 따라 모든 배열에 대해 반복하면 순서쌍의 합 중 최댓값이 answer, 최댓값이 되는 순서쌍의 개수가 count에 저장되므로 이를 출력해주면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    val N = nextInt()
    val sum = LongArray(N + 1)
    val map = HashMap<Int, IntArray>()
    for(i in 1..N){
        val a = nextInt()
        sum[i] = sum[i - 1] + a
        if(map.contains(a)) map[a]!![1] = i
        else {
            map[a] = intArrayOf(i, i)
        }
    }
    var answer = 0L
    var count = 0
    for(arr in map.values){
        val curSum = sum[arr[1]] - sum[arr[0] - 1]
        if(curSum > answer){
            answer = curSum
            count = 1
        } else if(curSum == answer) count++
    }
    println("$answer $count")
}