week3: 완전탐색과 백트래킹

[Taehyeon-Kim]

week3: 완전탐색과 백트래킹

[Taehyeon-Kim]

재귀를 이용한 모듈러 연산

// 11 모듈러 연산

let mod = 11
var ret = 0
let n = 10
let a = [24, 35, 38, 40, 49, 59, 60, 67, 83, 98]
var cnt = 0

func go(_ idx: Int, _ sum: Int) {
  // 이 조건 없으면
  // cnt => 1024번 반복
  // 이 조건 있으면
  // cnt => 10번 반복
  if ret == 10 { return }
  
  // 기저 사례
  if (idx >= n) {
    ret = max(ret, sum % mod)
    cnt += 1
    return
  }

  go(idx+1, sum + a[idx]) // 포함
  go(idx+1, sum)        // 미포함
}

func main() {
  go(0, 0)
}
main()

// 결과
print(ret, cnt)