[백준/Swift] 1806 : 부분합 문제 뿌수기!! + 2개 반례

 

 

• BOJ_1806.swift

• 1806 : 부분 합/ 문제 소개
• 풀이 과정
• 코드 구현

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

1806번: 부분합

1806 : 부분 합 / 문제 소개

 

길이 N(10 <= N < 100,000)짜리 10,000이하의 자연수로 이루어진 수열이 주어진다. 연속된 수들의 부분합 중에 그 합이 가장 짧은 것의 길이를 구하는 문제입니다.

풀이 과정

 

처음 제 접근법은

두 포인터 left,right 초기값을  0으로 잡아 주어진 수열을 투 포인터로 탐색해 나가는데

단 한번의 while문으로 부분합이 문제에서 주어진 최소 합보다 크면 left index ++, 작으면 right index ++를 하면서 sum과 수열 부분합 개수를 측정해 갔는데 틀렸습니다.

 

초기에 틀렸던 반례

5 11

1 2 3 4 5

ans = 11 , wrong = 15

 

이 경우 저의 코드는 left는 무조건 0인 상태에서 right만 ++하기에 sum의 상태는 1 -> 3 -> 6 -> 10 -> 15를 달성하고 right 가 maxIndex가 됬으므로 while문이 종료되어 left 탐색을 하지 못했습니다. 또한 이 경우 문제점이.. 최적의 값 2 4 5를 찾지 못하고 3 4 5를 답으로 측정했기 때문에 left는 무조건 순차적으로 증가시켜야 한다는 것을 알게 되었습니다.

---

그래서 for in 구문을 통해 0~n-1까지 left index를 두었을 때 right를 증가시키면서 left에 따른 right의 누적 합을 구해 나갔습니다. 또한 Right가 최소합을 만족시키면 더이상 right를 증가 시킬 필요가 없습니다. 최소합에서 더 커지는 경우 뿐이죠..

 

또 제가 미처 생각하지 못한 반례는

5 5

1 1 1 1 1

ans = 5, wrong = 0 

코드 구현

 

import Foundation

func BOJ_1806()
{
    let ns = readLine()!.split(separator:" ").map{Int(String($0))!}
    let n = ns[0], minSum = ns[1]
    let list = readLine()!.split(separator:" ").map{Int(String($0))!}
    
    var right = 0
    var ans = 100001
    var sum = 0
    
    for left in 0..<n
    {
        //최소 합보다 크면 minSum보다 크니까 더이상 sum을 구해나갈 이유가 없다.
        while sum < minSum && right < n
        {
            sum += list[right]
            right += 1
        }
        if sum >= minSum && ans > (right - left)
        {
            ans = right - left
        }
        sum -= list[left]
    }
    print(ans == 100001 ? 0 : ans)
}
BOJ_1806()

 

visit my github