[Swift 알고리즘] 백준 BOJ 1712 - 손익분기점

BOJ 1712 - 손익분기점

안녕하세요. 개발 중인 정주입니다.

 

오늘은 BOJ의 1712번 손익분기점 문제를 풀었습니다.

Swift로 처음으로 시간 복잡도를 생각했어야 하는 문제였습니다.

자세한 내용은 본문에서 보시죠.

---

Github

https://github.com/jeongju9216/swiftAlgorithm

 

문제 링크

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

 

---

풀이

이 문제의 시간 제한은 0.35초이고 input은 21억 이하입니다.

따라서 반복문 O(n)의 시간복잡도로는 문제를 풀 수 없습니다.

더 자세한 이야기는 코드를 보면서 설명하겠습니다.

바로 해답을 보고 싶은 분은 최종 코드의 설명을 봐주세요!

---

1차 코드

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
if input[1] > input[2] {
    print(-1)
} else {
    var cnt = 1
    while true {
        if (input[0] + input[1] * cnt) < (input[2] * cnt)  {
            break;
        }
        cnt+=1;
    }
    print(cnt)
}

반복문을 이용한 코드입니다.

최댓값을 고려하지 않고 문제를 풀어서 시간 초과가 났습니다.

C++ 기준으로 반복 1억 번 당 1초로 치환하여 풀면 되는데 최대 반복 횟수가 21억이니 당연히 시간 초과가 납니다.

따라서 이 문제는 O(n)의 시간복잡도가 아닌 O(1)의 시간복잡도로 문제를 해결해야 합니다.

---

최종 코드

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
if input[1] >= input[2] {
    print(-1)
} else {
    print(input[0] / (input[2] - input[1]) + 1)
}

O(1)의 시간복잡도로 푼 코드입니다.

손익분기점을 넘기 위해서는 순이익인 노트북 가격 - 가변 비용이 고정비용보다 많으면 됩니다.

따라서 순이익이 마이너스인 경우에는 -1을 출력하고 이외의 경우에는 나눈 몫에 1을 더해 출력하면 답이 됩니다.

---

마무리 인사

계속 사칙연산, 구현 문제만 풀다 오랜만에 최댓값이 억 단위인 문제를 푸니 시간 초과를 만나게 되었습니다.

방심하면 안 되겠습니다.

Swift로 알고리즘을 푸니 시간에 더욱 민감해지는 것 같습니다.

더 열심히 공부해야겠네요.

 

감사합니다!

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.