[프로그래머스] 숫자의 표현(수학) - ☆

#문제링크 : programmers.co.kr/learn/courses/30/lessons/12924

<전략>

1. 먼저, n이 홀수인 경우, 무조건 n/2 + (n/2 + 1)인 경우가 존재한다. 즉, n -> ㅁ+ㅁ (ㅁ는 빈자리)형태로 표현가능하다.

2. 차근차근 생각해보자. 각 숫자의 자리를 ㅁ으로 표현하겠습니다.

ⓐ 연속된 3개의 숫자의 합이 n일때,

ㅁ(ㅁ)ㅁ  -> 가운데 숫자는 n/3임이 자명하다. 괄호 안의 숫자 양 옆에 위치한 숫자 짝의 합 = 가운데 숫자 * 2

ⓑ 연속된 4개의 숫자의 합이 n일때, 

ㅁ(ㅁㅁ)ㅁ  -> 괄호 안의 숫자와 양 옆에 위치한 숫자 짝의 합이 모두 같다. 그리고 그 합은 홀수임이 자명하다.

ⓒ 연속된 5개의 숫자의 합이 n일때,

ㅁ(ㅁ(ㅁ)ㅁ)ㅁ  -> 가운데 숫자는 n/5임이 자명하다. 괄호 안의 숫자 양 옆에 위치한 숫자 짝의 합 = 가운데 숫자 * 2

. . .

위와 같은 특성으로 미루어보아,
연속된 (짝수)개의 숫자의 합이 n일때는, 괄호로 나뉜 숫자 짝의 합이 홀수이고, 결국 홀수의 배수가 된다.
예를들어, 22 = 4 ( 5 6 ) 7 은 5+6 = 4+7 = 11 로, 괄호로 나뉜 숫자 짝의 합이 11로 홀수이고, 22는 11의 배수가 된다.

연속된 (홀수)개의 숫자의 합이 n일때는, 가운데 숫자의 홀수의 배수가 된다.
예를들어, 24 = 7 ( 8 ) 9 를 보면, 괄호로 나뉜 숫자 짝의 합이 7+9 = 16 = 8*2로 가운데 숫자의 2배이고,
24는 가운데 숫자 8의 3배, 8 * 3으로 역시 3의 배수가 된다.

즉, 키워드는 홀수다. N의 약수 중에 홀수의 갯수만큼 연속합으로 표현가능한 수열이 반드시 존재한다.
홀수 하나당 연속합 수열 하나를 만든다고 보면 된다.
따라서, N을 홀수로 만든 후, 그 홀수의 약수의 갯수를 세어주면 된다. 단, 1과 자기자신을 포함해야 한다.
15로 예를 들었을때, 약수 1은 15*1자체로 이미 연속된 숫자의 합인 조건을 충족하므로 그렇고, 15도 포함하는 이유는 맨처음에 언급했던, 모든 홀수는 ㅁ+ㅁ 꼴로 표현이 가능하기 때문에, 이 경우(두개로 쪼개는)를 약수 15의 경우로 셈해서 그렇다.

Code