안녕하세요! 알고리즘 질문 드립니다.
조회수 2722회
-
(•́ ✖ •̀)
알 수 없는 사용자
2 답변
-
문제를 풀려면 두 가지 방향으로 고민하면 될 것 같네요.
첫 번째는, 삼각수 K보다 작은 Tn 을 구하는 것을 생각해야겠네요.
Tn = n(n+1)/2 임으로 n(n+1)/2 < K 를 대충 풀어보면 되겠네요.
2차방정식의 근의 해를 통해서 n(n+1) < 2K 의 해를 구해보면, n < ( sqrt(1+8K) - 1 ) / 2 이 될겁니다.
위를 통해서, K보다 작으면서 가장 큰 Tn을 만드는 삼각수 n을 이제 알고 있습니다.
두 번째는 가장큰 삼각수 1에서 n까지의 숫자 3개를 선택하여 각 삼각수를 더할 때, K가 만들어지는 방법을 생각하면 되겠네요.
-
가장 단순한 해결방법은,
입력값 N에 대해서,
- N보다 작은 삼각수들을 구한다.
- 삼각수들을 전부 더하면서 해당하는 수가 나오는지 찾는다.
-
(•́ ✖ •̀)
알 수 없는 사용자
댓글 입력