안녕하세요! 알고리즘 질문 드립니다.


다음과 같은 문제인데 어떤식으로 풀어야될지 잘 모르겠습니다. 어떻게 풀어야 될까요? 고수님들 답변 부탁드립니다!이미지 이름이나 설명을 여기에 넣어주세요.

이미지 이름이나 설명을 여기에 넣어주세요.

  • 2016년 04월 15일에 작성됨

조회수 335


2 답변


좋아요
1
싫어요
채택취소하기

문제를 풀려면 두 가지 방향으로 고민하면 될 것 같네요.

첫 번째는, 삼각수 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가 만들어지는 방법을 생각하면 되겠네요.

  • 2016년 04월 15일에 작성됨
    리눅스(유닉스) 기반의 시스템에서 웹 서비스를 개발하고 있습니다.


가장 단순한 해결방법은,

입력값 N에 대해서,

  1. N보다 작은 삼각수들을 구한다.
  2. 삼각수들을 전부 더하면서 해당하는 수가 나오는지 찾는다.
  • 2016년 04월 15일에 작성됨
    Node.js based full stack web developer. Studying scala language.

로그인이 필요한 기능입니다.

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 작성한 답변에 다른 개발자들이 댓글을 작성하거나 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.
► 로그인
► 계정만들기
Close