백준 2632 피자판매

출처: www.acmicpc.net/problem/2632

분류: 이분탐색

---

접근방식

이분탐색을 통해 해결해볼 수 있었습니다.

전체적인 풀이 과정은 다음과 같습니다.

1. 각 피자에서 가능한 피자 조각을 모두 구한다. (n == 1000 이므로 n^2 이면 충분합니다.)

2. 한쪽 피자에서 선택했을 경우 또는 하지 않을 경우 다른 쪽 피자의 값이 무엇이 되어야 할지 기대할 수 있기 때문에 이를 이분탐색으로 파악합니다.

 

가능한 피자 조각을 구할 때 주의해야 할 점은 피자 조각이 원형이라는 점입니다.

주어진 예제처럼 2 2 1 7 2 에서 피자 조각 경우를 구할 때, 원형으로 생각을 해줘야 합니다.

2 2 1 7 2  - 여기서 1부터 시작한다면 가능한 조합은 

[1], [1, 7], [1, 7, 2], [1, 7, 2, 2], [1, 7, 2, 2, 2] 

이 됩니다! 단 이때 마지막 5가지를 모두 선택하는 경우는 중복되니까 한 번만 포함시켜줘야 합니다.

저는 n-1 까지만 조합을 만들어주고 마지막에 한 번만 5가지를 모두 더한 조각을 추가해주는 방식으로 해결했습니다.

원형은 % 연산을 사용해서 해결해줄 수 있습니다.

for i in 0..<arr.count {
  var temp = 0
  for j in i..<i+arr.count-1 {
    temp += arr[j % arr.count]
    table[temp, default: 0] += 1
  }
}

그리고 저는 중복되는 건 딕셔너리로 개수만 체크해서 처리해줬습니다 :)

이때는 a와 b 에서 원하는 조각 조합을 찾았으면

a 에서 피자 조각 개수 * b에서 피자 조각 개수

로 처리를 해줘야겠죠?

 

해결방법

일단 a 조합에서 n까지를 돌면서 원하는 피자조각 - an 이 b에서 있나 쭉 확인을 했는데

b 에서만 원하는 피자 조각이 또 있는지 확인해줘야 해서 포문을 나오고 한 번 더 처리를 해줬습니다,.

더 효율적으로 처리할 수도 있을 거 같네요 @_@

 

let n = Int(readLine()!)!
let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
var a = [Int]()
var b = [Int]()
for _ in 0..<nm[0] {
  a.append(Int(readLine()!)!)
}

for _ in 0..<nm[1] {
  b.append(Int(readLine()!)!)
}

func sum(_ arr: [Int]) -> [Int: Int] {
  var table = [Int: Int]()
  for i in 0..<arr.count {
    var temp = 0
    for j in i..<i+arr.count-1 {
      temp += arr[j % arr.count]
      table[temp, default: 0] += 1
    }
  }
  table[arr.reduce(0, +), default: 0] += 1
  return table
}

let aTable = sum(a)
let bTable = sum(b)

let sumA = [Int](aTable.keys).sorted()
let sumB = [Int](bTable.keys).sorted()

var resultCase = 0

for an in sumA where an <= n  {
  guard an != n else {
    resultCase += aTable[an]!
    break
  }
  
  if let bn = binarySearch(n-an) {
    resultCase += aTable[an]! * bTable[bn]!
  }
}

if let bn = binarySearch(n), let bCase = bTable[bn] {
  resultCase += bCase
}

func binarySearch(_ target: Int) -> Int? {
  var low = 0
  var high = sumB.count-1
  
  while low <= high {
    let mid = (low + high) / 2
    
    if sumB[mid] == target {
      return sumB[mid]
    } else if target < sumB[mid] {
      high = mid-1
    } else {
      low = mid+1
    }
  }
  
  return nil
}

print(resultCase)

 

배운점

피자조각 개수를 미리 구해놓는 데서 머리가 좀 안 굴러갔는데

찬찬히 적어가면서 이해를 했다.

메모메모..!