[백준 10986][swift] 나머지합

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

 

입력과 출력

 

요구 개념

• 누적합: Prefix Sum(앞쪽에서부터 합을 누적)
• 수학: 순열과 조합(permutation, combination)

누적합의 개념

설명

i 부터 j+1 번째까지합을 수식으로 나타내면 preFix[j+1]-preFix[i]가 된다. 그 연속된 구간(i~j+1)의 누적합을 m으로 나누었을 때 0 이 되는 조합의 갯수를 출력해야한다. (dp[i] 와 preFix[i] 는 같다)

첫 시도 - 완전 탐색 [시간초과]

이중 For문을 순회하면서 i<j+1 인 관계를 만들어주면서 (preFix[j+1]-preFix[i])%m == 0 일 때 count += 1 을 해주었다. 

for i in 1..<dp.count {
    for j in 0..<i {
        if (dp[i]-dp[j]) % m == 0 {
            count += 1
        }
    }
}

두 번째 시도 - 이차원 배열에서의 완전 탐색 [메모리 초과]

배열 하나로 다 담으려는 첫 번째 시도에서 실패하자, 왠지모르게 2차원 배열로 하고 싶은 마음이 들었다. 

dp[0] 과 dp[i][0] 은 모두 0으로 비워놓고 2차원 배열을 만들어보았다. 뭔가 저렇게 수기로 적고 나니 규칙성이 보이는 것 같았다. 

그래서 이런 수식을 만들어 낼 수 있었다. 

if i - 1 == j {
	dp[i][j] = dp[i][j-1] - arr[j]
} else { 
	dp[i][j] = dp[i-1][j] + arr[i]
}

위의 사진에서 행을 이동할 때는 else 문을 사용했고, 열을 이동할 때는 if 조건문을 사용했다. 

지금 보니까 그냥 시간만 낭비한 것 같다. 아쉽지만 로직으로 맞지도 않았다. 그래도 나름 해볼만한 코드였다. 

세 번째 시도  - 답지를 봄 

수학적인 개념이 들어가있었다. 중학생때 배운 교환 법칙을 사용하고 있었다. 

중학교 수학 사용

a와 b의 차를 m 으로 나눈 나머지가 0 이라면 우리가 찾으려는 숫자의 조합이다. 중심 개념은 "a를 찾으면 b는 찾은 것"이다. 이게 무슨 말이냐면, 

(a-b) % m = 0   <- 분배 법칙

(a%m)-(b%m) = 0 <- 교환 법칙

a%m = b%m 

최종적으로 이런 식이 나온다. 이것을 우리가 찾은 식 (preFix[j+1]-preFix[i])%m 에 적용을 하면 된다. 

순열과 조합 사용

뭐 그렇다고 뭐가 어쨌다는 것인가? 저것을 찾아서 count 배열에 1씩 더해도 달라지는 것은 없지 않은가? 라고 생각했다면 아래를 좀 더 보자. 

var counter = [Int](repeating: 0, count:m)

for i in 0..<arr.count {
    //MARK: - 누적합을 채우는 부분
    if i == 0 {
        preFix[i] = arr[0]
    } else {
        preFix[i] = preFix[i-1] + arr[i]            
    }
    
    //MARK: - counter에 값을 추가하는 부분
    counter[preFix[i]%m] += 1 
}

여기서 counter 는 모듈러 연산을 담기 위해 m의 개수만큼 배열로 선언했다. 

즉 counter[0] 은 구간합(a)를 m으로 나눈 나머지가 0인 숫자가 있으면 + 1 을 더해준 것이다. 

그런데 두 번째 시도에서는 2차원 배열을 할 정도로 연산의 개수가 많았는데 여기서는 1차원 배열에 끝내고 있어서 이해하는데 많은 시간이 걸렸다. 여기서 신기한 부분이 있다. 나머지의 개수를 저장한 배열을 만드는 이유는 이를 통해서 조합을 할 수 있기 때문이다. 

아까 a % m 을 하나 구하면 b % m 은 구한 것과 같다 라고 이야기한 부분을 여기서 증명할 수 있다. 

관계가 좌항이 있으면 우항도 반드시 있는 1:1 관계이기 때문이다. 

거기다가 a는 b와 중복이 되지 않기 때문에(j+1 > i) 조합을 사용할 수 있다. 

구간합의 값 중 2개를 뽑아서 조합하는 것이다. 4C2 를 구하면 되는데, 이를 구하기 위해서는 

4P2 / 2 를 해야한다. 이를 구하는 수식은 4 * 3 / 2 이고 이것을 일반화 하면 n * (n-1) / 2가 나온다.

즉, 구간합을 m으로 나눈 값이 0 인 구간합이 있다면 counter[preFix[i]%m] += 1 을 한 것이다. 

그리고 조합을 할려면 그 개수를 a라고 하면 b는 자동적으로 a-1이 된다. 

    var result = 0
    for i in 0..<m { 
        result += (counter[i] * (counter[i]-1)) / 2
    }
    return result + counter[0]

result에 조합의 개수를 담고 최종적으로 counter[0], (m으로 나눈 나머지가 0인 구간합의 개수)를 더해주면 완성이다.

최종 코드 

func solution() -> Int {
    let nm = readLine()!.split(separator: " ").map { Int($0)! }
    let arr = readLine()!.split(separator: " ").map { Int($0)! }
    let m = nm.last!
    let n = nm.first!
    var preFix = [Int](repeating: 0, count: n)
    var counter = [Int](repeating: 0, count: m)
    
    for i in 0..<arr.count {
        if i == 0 {
            preFix[i] = arr[0]
        } else {
            preFix[i] = preFix[i-1] + arr[i]            
        }
        counter[preFix[i]%m] += 1   
    }
    
    var result = 0
    for i in 0..<m { 
        result += (counter[i] * (counter[i]-1)) / 2
    }
    return result + counter[0]
}

print(solution())

 

세줄 요약

1. 중학교와 고 1수준의 수학, 누적합을 사용한 알고리즘 문제이지만 답지를 봐야 풀 수 있었다. 생각하는 힘(문제해결력)을 길러야한다.

2. 3시간 30분 정도 소요. 차차 나아질 것이다. 

3. 이 문제 해설을 내가 쓰긴 했지만 나중에 다시 보면 무슨말을 하는지 이해하기 어려울 것 같다.
    글 잘쓰는 사람이 개발도 잘한다는 말이 여기서 와닿는다.

 

답지 출처

"개발자지망생 조안이"님 블로그 https://sapjilkingios.tistory.com/entry/Swift누적합-백준-10986번-나머지-합