parkgunwon1   1년 전

직감적으로 찾았긴했는데 잘 모르겠네요 ㅠㅠ

lycoris1600   1년 전

딱 봤을 때 드는 생각은, 2와 3으로만 배열을 구성할 수 있을 것 같네요.
3^2이 2k_1 개, 2^2가 3k_2개 존재하면 되는데, 그럼 k_1!=0, k_2!=0, 2k_1+3k_2=N을 만족시키는 k_1, k_2를 찾는 문제가 됩니다

7 이상의 N에 대해서는 반드시 답이 존재한다는 것을 증명할 수 있죠.
그럼 N이 2부터 6까지인 경우에 대해서 생각하면 되는데 이 경우는 그냥 브루트포스 돌려서 알아내도 될 것 같네요. 150 이하의 소수는 35개밖에 존재하지 않습니다.

parkgunwon1   1년 전

답변 감사합니다 그냥 정답들이  2 2 3 17 이면 2제곱 + 2제곱 + 3 제곱 = 17 이런식으로 뭔가 신기한 일이 발생하지만 이런 것이 안되는 경우가 있어서 브루트포스말고 뭔가 특별한 방법이 있나 궁금했습니다

yyyy7089   1년 전

전 백트래킹 짜서 찾았어요

lycoris1600   1년 전

크기가 크면 답이 자명하므로 크기가 작은 경우에 대해서만 완전탐색을 해보면 됩니다.

저는 파이썬의 itertools.combinations_with_replacement를 써서 찾았습니다.

parkgunwon1   1년 전

크기가 클때 답이 자명하다는걸 증명 할 수 있나요?

lycoris1600   1년 전

2와 3으로만 배열을 구성할 수 있음을 위에서 보이지 않았나요?

최종 배열에서 2의 개수가 x개, 3의 개수가 y개라고 합니다.
예를 들어, x=3, y=2라면 답은 [2,2,2,3,3]입니다.

전체 배열이 2로 나누어떨어지려면 y는 2의 배수여야 합니다. 따라서 y=2k_1이라고 두겠습니다.
전체 배열이 3으로 나누어떨어지려면 x는 3의 배수여야 합니다. 따라서 x=3k_2라고 두겠습니다.

저희는 2k_1+3k_2=N을 만족시키는 (k_1,k_2)의 순서쌍을 찾아야 합니다.
이때, (N-2), (N-4), (N-6) 중 적어도 하나는 3의 배수입니다. (N에 3p+0, 3p+1, 3p+2를 각각 대입해 보시기 바랍니다.)
따라서 N이 충분히 크다면, k_1에 1 2 3 중 하나의 값을 넣었을 때 음이 아닌 정수 k_2를 얻어낼 수 있습니다.

parkgunwon1   1년 전

아 질문은 당연할걸 뇌빼고 질문했네요 무식한 질문에 답변 감사합니다 ㅋㅋㅋ

댓글을 작성하려면 로그인해야 합니다.