문제 1006 원기둥에 공 쌓기
[만든사람 : ]
문제 설명
N개의 원기둥에 1부터 무한대까지의 정수가 적혀있는 공을 쌓는 게임을 하려한다. 이 게임의 목표는 최대한 많은 공을 쌓는 것이다. 단, 공을 쌓을 때에 규칙이 하나 있는데 그것은 위아래로 이웃하는 두 공의 합이 완전제곱수(어떤 정수를 제곱한 수)가 되어야 한다는 것이다. 아래 그림은 기둥의 수가 4개 일 때 원기둥에 최대한 많은 공을 쌓은 모습이다.
원기둥의 개수 N을 입력받아 최대로 쌓을 수 있는 공의 개수를 출력하는 프로그램을 작성해 보자.
▶처리조건
(1) 공은 1번부터 시작해서 한 번에 하나씩 번호가 커지는 순서로 쌓는다.
(2) 원기둥에 쌓을 수 있는 공의 개수가 무한하면 -1을 출력하고, 그렇지 않을 경우는 쌓을 수 있는 최대 공의 개수를 출력한다.
(3) 입출력에 사용되는 값은 정수이며, 입력되는 원기둥의 수 N은 10,000이하의 양의 정수이다.
입력 설명
원기둥의 수를 입력받는다.
출력 설명
최대로 쌓을 수 있는 공의 수를 출력한다.
입력 예시 복사
4
출력 예시 복사
11
출처/분류