[문제풀이] int, long long 오버플로우, 시간초과 관련 미세 팁

int 자료형으로 표현 가능한 숫자는 210,000,000(21억) 언저리까지이다. 그 이상의 숫자는 오버플로우가 발생하므로 long long 자료형을 사용해야 한다. 내가 코딩하다가 숫자가 21억이 넘어갈지 안 갈지 어떻게 알아??라는 의문이 들 수 있다.

 

1. 먼저 알고리즘을 생각해본다. 사람마다 다르지만 나는 퍼수도코드로 짜고 시작한다.

2. 시간복잡도를 생각해본다. O(N*M) 이런 식으로 나온다면 N과 M의 최댓값을 기준으로 곱해서 생각하면 된다. 얼추 21억이 넘겠다 싶으면 안전하게 long long으로 짜는 편이 좋다.

3. long long으로 코드를 바꿀 때 콤팩트하게 확실하게 안 바꿔도 되는 자료형을 제외하고는 다 바꾸는 편이 좋다. 연산 중 자동 형변환이 일어날 수 있다.

 

시간초과도 비슷하다. 10^9연산이 대충 1초 정도라고 생각하면 된다. 로컬에서 예제를 최댓값으로 다 입력해 보고 대충 몇 초가 걸리는지 생각해 보는 것도 좋은 방법이다.