유레카 이론

문제

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

유형

• 수학
• 브루트포스 알고리즘

풀이

브루트포스로 모든 수를 검사해서 그 수를 만들 수 있으면 1을 출력하도록 했다. input까지 포함하면 4중 포문을 사용했는데.. 다른분들이 푼 시간과 내가 푼 시간이 차이가 커서 개선했다.

1. 먼저 t 배열에 1000이하의 삼각수를 모두 넣어줬었는데 그러면 수가 얼마여도 for문이 44 ^ 3 만큼 돌기 때문에 num보다 작은 수까지만 t 배열에 추가해주는 식으로 바꿨다.
2. 수를 만들 수 있는 방법이 존재하면 루프를 탈출하는 식으로 코드를 개선했다.

소스코드

기존 풀이

var t: [Int] = []
let n = Int(readLine()!)!
for i in 1...44 {
    let sum = (i * (i + 1)) / 2
    t.append(sum)
}
for _ in 0..<n {
    let num = Int(readLine()!)!
    var isSuccess = false
    for i in 0..<t.count {
        for j in 0..<t.count {
            for k in 0..<t.count {
                if t[i] + t[j] + t[k] == num {
                    isSuccess = true
                }
            }
        }
    }
    isSuccess == true ? print(1) : print(0)
}

개선한 풀이

let n = Int(readLine()!)!

for _ in 0..<n {
    let num = Int(readLine()!)!
    var t: [Int] = []
    
    for i in 1...44 {
        let sum = (i * (i + 1)) / 2
        t.append(sum)
        if sum > num {
            break
        }
    }
    var isSuccess = false
    for i in 0..<t.count {
        for j in 0..<t.count {
            for k in 0..<t.count {
                if t[i] + t[j] + t[k] == num {
                    isSuccess = true
                }
            }
        }
    }
    
    isSuccess == true ? print(1) : print(0)
}