[2632] 피자판매

toru·2022년 9월 25일
0
배열이 원으로 이어저 있으니 순열을 구하면 0..<n의 합에서 n-1만큼의 중복이 생긴다. 
이를 따로 처리해준다.
// 투포인터
let target = Int(readLine()!)!
let p = readLine()!.split(separator: " ").map{Int(String($0))!}
let (a,b) = (p[0],p[1])
var arrA = [Int]()
var arrB = [Int]()
var sumA = [0]
var sumB = [0]
var s = 0
var e:Int
var cnt = 0

for _ in 0..<a {
    arrA.append(Int(readLine()!)!)
}
for _ in 0..<b {
    arrB.append(Int(readLine()!)!)
}

func getSum(_ ab:Int,_ arr:[Int],_ sum:inout[Int]) { // 원형 순열?
    for i in 0..<ab {
        var temp = 0
        for j in i..<ab+i-1 {
            temp += arr[j%ab]
            sum.append(temp)
            }
        }
    sum.append(arr.reduce(0,+))
}
getSum(a, arrA, &sumA)
getSum(b, arrB, &sumB)
sumA.sort()
sumB.sort()
e = sumB.count-1
    
while s < sumA.count, 0 <= e {
    let sum = sumA[s] + sumB[e]
    if sum == target {
        let A = sumA[s]
        let B = sumB[e]
        var cntA = 0
        var cntB = 0
        while s < sumA.count, sumA[s] == A {
            s += 1
            cntA += 1
        }
        while 0 <= e, sumB[e] == B {
            e -= 1
            cntB += 1
        }
        cnt += cntA * cntB
    }
    else if sum < target {
        s += 1
    }else {
        e -= 1
    }
}
print(cnt)
profile
iOS

0개의 댓글