[BOJ 1339- 단어수학] 시간초과 원인(Math.pow 가 병목의 원인)

위는 빠른 버전이고 아래는 느린버전이다.

최대 8자리수의 합을 구할때 빠른버전의 경우 최대 8번의 반복문을 돈다.

느린버전의 경우 Math.pow 내부에서 지수부분만큼 반복문을 돌게되므로

1+2+3+4+...+8 = 36번 돌게 된다.

위 문제를 백트레킹 방식으로 풀이할경우,

빠른버전의 경우 시간 복잡도는 10! * (8*10)*8이 되고

느린버전의 경우 시간 복잡도는 10! * (8*10)*36이 된다.

시간 제한이 2초 이기 때문에 시간이 아슬아슬하게 통과된다.

이 경우 무리하게 백트레킹으로 풀이하려고 하기 보다는 다른 풀이를 생각하는것이 안전하다고 생각한다.