문제출처 : https://www.acmicpc.net/problem/10448
1. 문제요약
- Tn = n(n+1)/2
- 자연수 K가 주어졌을 때 세개의 Tn 으로 나타낼 수 있으면 1, 없으면 0
- 3 <= K <= 1,000
2. 접근방법
- Tn이 몇개나 필요할까? => n(n+1)/2 <= 1,000 을 만족하는 n은 대충 44, 45
- T1 ~ T45 까지 3개를 뽑으면 되므로 45 * 45 * 45 = 91,125 이므로 1초 내에 들어옴
- 즉, 브루트 포스
- 여기서 45 * 45 * 45는 중복이 포함
- T1 + T1 + T2 / T1 + T2 + T1 / T2 + T1 + T1 은 같은 경우 이므로 제외 하면 조금 더 빨라 지겠지?
※ 실제로 다 해본 경우는 32ms / 중복 제외한 경우는 28ms
3. 시간복잡도
- N^3 = 91,125
4. 회고
- 미리 결과 합을 구해두면 출력에 편함
- 어차피 시간내에 들어오므로 굳이 안해도 됨
- 미리 구한 다른 사람은 0ms 인데 난 왜 28ms 이냐!!!
- 싱크 안맞춘 cin 때문인가.... T의 갯수가 몇개인지 모르니
- 미리 세개의 합을 구한 배열을 지역변수에서는 T45 + T45 + T45 = 3105 이상으로 잡아야 오버 인덱스 안남
전역변수로 선언한다면 100 개 정도는 더 잡아주는 거 같음 3000개로도 통과되네
소스코드
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
'먹고살려면 > boj' 카테고리의 다른 글
BOJ 1325 효율적인 해킹 (0) | 2017.12.27 |
---|---|
BOJ 2667 단지번호붙이기 (0) | 2017.12.27 |
BOJ 2231 분해합 (0) | 2017.12.26 |
BOJ 1966 프린터 큐 (0) | 2017.12.26 |
BOJ 7568 덩치 (0) | 2017.12.19 |