[JS] PGM 181935 홀짝에 따라 다른 값 반환하기

문제 바로가기

결과

function solution(n) {
    var answer = 0;
    
    if(n % 2 == 1) { for(let i = 1; i <= n; i += 2){answer += i} }
    else { for(let i = 2; i <= n; i += 2){answer += Math.pow(i, 2)} }
    return answer;
}

• 시간: 0.04ms
• 메모리: 33.5MB

---

문제 분석

1. n이 홀수 이면 n이하 홀수들의 합 구하기
2. n이 짝수이면 n이하 짝수들의 제곱의 합 구하기

---

접근 방법

1. n이 홀수일 때와 짝수일 때 결과 출력 분기 처리
2. 각 조건문에 대한 for문 적용

---

배운 점

제곱 구하기

n이 짝수인 경우 짝수들의 제곱의 합을 구해야한다.
Math.pow(base, exponent) 내장함수를 활용 할 수 있다.

for(let i = 2; i <= n; i += 2){answer += Math.pow(i, 2)}

다른 풀이 참고해보기

등차수열의 합과 자연수 거듭 제곱의 합 공식을 활용한 멋진 풀이법을 봤다.
조건문과 반복문을 사용하지 않고 문제를 푼 점이 인상 깊었다.

부끄럽지만 수포자였기 때문에 공식을 잘 모른다.
나중에 다른 문제 풀이에도 활용 할 수 있도록 공식에 대해 공부해보았다.

function solution(n) {
    if(n%2===1)
      return  (n+1)/2*((n + 1)/2) ;
    else
      return   n*(n+1)*(n+2)/6;
}

1) n이 홀수일 때 등차수열의 합 공식 적용하기

공식 이해에 도움받은유튜브 링크

등차수열이란 '차이'가 일정한 수열을 의미한다.

n이 홀수일 때, n이하의 정수 중 홀수인 정수의 모든 합을 구해야한다.
n이 만약 9라면 1, 3, 5, 7, 9 들의 합이 필요하다.

1 + 3 + 5 + 7 + 9
9 + 7 + 5 + 3 + 1

각 정수들을 정방향과 역방향으로 나열하고 위 아래를 더하면
각 쌍의 합이 10으로 동일하게 나온다.

10 * 5 == (첫항 + 끝항) * 항의 개수
위의 식을 결과로 윗줄과 아랫줄을 모두 합한 합인 50을 구할 수 있다.
한 줄의 합을 구하려면 절반으로 나누어주면된다.

결국 n이 구일 때 등차수열의 합을 구하는 공식은 아래와 같아진다.
(1 + 9) * 5 / 2 = 25

여기서 또 한가지 발견한 사실이 있다.
산출 결과인 25는 항의 개수의 제곱과 같다.
5**2 = 25

n이 7이라고 가정해보자.
n이하 홀수의 개수는 총 4개 이며, 4의 제곱인 16이 결과로 나와야한다.
(1+7) * 4 / 2 = 16

그렇다면 홀수인 항의 개수는 어떻게 구해야할까?
첫항과 끝항의 합에서 절반을 나누어 구할 수 있다.

n이 9라면 (1 + 9) / 2 = 5
n이 7이라면 (1 + 7) / 2 = 4

따라서 홀수인 n의 수가 주어졌을 때 모든 항의 합을 구하는 계산식은 아래와 같다.
(n + 1) * ((n + 1) / 2) / 2

위 식을 좀더 간결하게 항의 개수의 제곱으로 변경하면 아래와 같다.
((n + 1) / 2)**2

---

2) 자연수 거듭 제곱의 합 공식 이해하기

공식 이해에 도움받은 유튜브 링크

1~4까지 모든 항의 제곱의 합을 구하려면 아래와 같은 식을 세울 수 있다.
$\boxed {S(5) = 1^2 + 2^2 + 3^2 + 4^2 + 5^2}$

S(5)는 1의 제곱인 1, 2의 제곱인 4에 1을 더한 5,
3의 제곱인 9에 5를 더한 14, 4의 제곱인 16에 14를 더한 30, ...
이렇게 순차적으로 값이 변환될 것이다.

// 1차 차이
1 -> 5 -> 14 -> 30 -> 55
  (4)  (9)  (16)  (25)

앞,뒤 숫자는 괄호안의 숫자와 같이 불규칙한 차이 값이 발생한다.
자세히보니 $2^2$ $3^2$ $4^2$ $5^2$ 의 값과 일치한다.

// 2차 차이
4 -> 9 -> 16 -> 25
  (5)  (7)  (9)

$n^2$ 값들의 차를 비교해보니 또 불규칙한 차이 값이 발생한다.

// 3차 차이
5 -> 7 -> 9
  (2) (2)

다시 그 값들의 차를 구해보니 '2'라는 일정한 차이가 발생한다.

---

차이를 구하는 과정을 수식으로 나타내보자.

S(1) = 1, S(2) = 5, S(3) = 14, S(4) = 30, S(5) = 55

위와 같은 수열을 함수 f(n)이라고 부른다면, f(n) = S(n)와 같이 표현 할 수 있다.

1차 차이

1 -> 5 -> 14 -> 30 -> 55

단계별 차이를 계산하는 식은 아래와 같다.

1. 5 - 1 = $(1 + 1)^2$
2. 14 - 5 = $(2 + 1)^2$
3. 30 - 14 = $(3 + 1)^2$
4. 55 - 30 = $(4 + 1)^2$

위 과정을 수식으로 쓰면, f(n + 1) - f(n) 와 같다.

1번을 예로 들어 n의 값이 1이라면,
5 - 1이라는 계산 식은 f(1 + 1) - f(1) = S(2) - S(1)로 결과를 산출한다.
다시 S(2) - S(1) = 4 즉, 2의 제곱이 된다.

위와 같은 과정을 아래와 같은 수식으로 다시한번 표기할 수 있다.
$\boxed{ f(n + 1) - f(n) = (n + 1)^2 }$

결국 1차 차이는 $(n + 1)^2$ 가 되고,
전개 공식( $(a+b)^2 = a^2 + 2ab + b^2$ )을 적용하여 $n^2 + 2n + 1$ 이 된다.
최고 거듭제곱은 '2'이므로 2차식이 됨을 알 수 있다.

2차 차이

4 -> 9 -> 16 -> 25

1차 차이에 다시 차이를 구하는 식은 아래와 같다.

1. 9 - 4 = $(1 + 2)^2 - (1 + 1)^2$
2. 16 - 9 = $(2 + 2)^2 - (2 + 1)^2$
3. 25 - 16 = $(3 + 2)^2 - (3 + 1)^2$

위 과정을 수식으로 쓰면, $(n + 2)^2 - (n + 1)^2$ 와 같다.
2차차이에도 전개 공식을 적용하면, 아래와 같다.

$(n + 2)^2 = n^2 + 4n + 4$
$(n + 1)^2 = n^2 + 2n + 1$

$(n^2 + 4n + 4) - (n^2 + 2n + 1) = 2n + 3$

최고 거듭제곱은 '1'이므로 1차식이 됨을 알 수 있다.

3차 차이

5 -> 7 -> 9

2차 차이에 다시 차이를 구하는 식은 아래와 같다.

1. 7 - 5 = 2
2. 9 - 7 = 2

2차 차이의 값(2n + 3)을 기반으로 수식화 하면, 아래와 같다.
(2(n + 1) + 3) - 2n + 3

이렇게 3차 차이의 값은 '2'로 상수로 만들어졌다.

---

위의 과정을 통해 자연수 제곱의 합을 구할 때 3차식이 필요하다는 것을 알아냈다.
3차식을 일반형 공식으로 계산하는 과정은 아래와 같다.
$\boxed{ S(n) = an^3 + bn^2 + cn }$

위에서 구했던 S(1) = 1, S(2) = 5, S(3) = 14 값을 활용하여 a, b, c 계수를 구해보자.

1. n = 1
=> a + b + c = 1

2. n = 2
=> 8a + 4b + 2c = 5

3. n = 3
=> 27a + 9b + 3c = 14

위에도 도출된 식을 활용해 연립 방정식으로 계수를 구해보자.

// a 구하기

// step.01
2a + 2b + 2c = 2 // 1번 식에 2를 곱한다.
(8a + 4b + 2c) - (2a + 2b + 2c) = 3 // 2번과 1번 식의 차를 구한다.
6a + 2b = 3 // step.01 도출 결과

// step.02
3a + 3b + 3c = 3 // 1번 식에 3을 곱한다.
(27a + 9b + 3c) - (3a + 3b + 3c) = 11 // 3번과 1번 식의 차를 구한다.
24a + 6b = 11 // step.02 도출 결과

//step.03
18a + 6b = 9 // step.01 도출 결과에 곱하기 3
(24a + 6b) - (18a + 6b) = 2
6a = 2

a = 2

// b 구하기
6(1/3) + 2b = 3 // a 구하기 step.01 도출 결과 응용
2 + 2b = 3
2b = 1

b = 1/2

// c 구하기
1/3 + 1/2 + c = 1 // 1번 식 
5/6 + c = 1

c = 1/6

위와 같은 과정을 통해 도출된 a, b, c를 일반형 공식에 대입하면 아래와 같다.
$\boxed{ S(n) = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n }$

계산하기 쉽게 통분해서 정리해보자.
$\boxed{ S(n) = \frac{2n^3 + 3n^2 + n}{6} }$

인수분해를 통해 분자 값을 정리해보자.
$\boxed{ S(n) = \frac{n(n+1)(2n+1)}{6} }$

3) n이 짝수일 때 자연수 거듭 제곱의 합 공식 적용하기

n이 짝수일 때, n이하의 정수 중 짝수인 정수의 모든 합을 구해야한다.
n이 만약 10라면 2, 4, 6, 8, 10 들의 합이 필요하다.

n이하의 정수를 나열한 것은 아래와 같이 나타낼수도 있다.
$\boxed{ 2 = 2×1, 4 = 2×2, 6 = 2×3, 8 = 2×4, 10 = 2×5 }$

위 규칙을 2k라는 수식으로 표현 할 수 있다.
n의 최대값인 10을 수식으로 변환하면, k의 값은 5로 2k = n 으로 표현 할 수 있다.
짝수 n의 개수 또한 $\frac{n}{2}$ 로 계산 할 수 있으며, 결국 k의 최대값은 $\frac{n}{2}$ 가 된다.

$\boxed{ \frac{m(m+1)(2m+1)}{6} }$
자연수 거듭 제곱의 합 공식을 위와 같이 세웠을 때, 최댓값을 활용해 연속된 수들의 제곱의 합을 구할 수 있으니
이 전에 구한 k의 최댓값인 ' $\frac{n}{2}$ ' 를 m에 대입한다.

여기서 또 하나의 과정을 추가해주어야한다.
먼저 n이하의 모든 짝수 제곱의 합을 구하는 식은 아래와 같다.
$2^2 + 4^2 + 6^2 + ... + n^2$

현재 m에는 $\frac{n}{2}$ 가 적용되어 있으므로, 아래와 같은 식이 세워져있다.
$1^2 + 2^2 + 3^2 + 4^2 + 5^2$

우리가 원하는 답을 구하려면 위 식에서 나온 결과에 4를 곱해주어야한다.
위 과정을 시그마로 표현해보면 아래와 같다.

자연수 거듭 제곱의 합 공식
$\boxed{ \sum_{k=1}^{m} k^2 = \frac{m(m+1)(2m+1)}{6} }$

k는 1부터 시작되며, m은 마지막 k 값이된다.
'짝수인 자연수'라는 조건이 붙으면 k의 값은 1부터 $\frac{n}{2}$ 까지 이므로,
1. m은 $\frac{n}{2}$ 로 대입되어야한다.
2. 짝수를 2k로, 짝수의 제곱을 $(2k)^2$ 로 표현해야한다.

조건을 적용한 공식을 시그마로 표현하면 아래와 같다.

1. 짝수인 자연수 거듭 제곱의 합 공식
   $\boxed{ \sum_{k=1}^{m} 4k^2 = \frac{m(m+1)(2m+1)}{6} }$

2. 4는 상수이니 밖으로 꺼내보자.
   $\boxed{ 4 \sum_{k=1}^{m} k^2 = \frac{m(m+1)(2m+1)}{6} }$

3. m에 $\frac{n}{2}$를 대입해보자.
   $\boxed{ \frac{4}{6} \times \frac{n}{2} \times \left(\frac{n}{2}+1\right) \times (n+1) }$

4. 위 식을 좀 더 정돈해보자.
   $\boxed{ \frac{2}{3} \times \frac{n}{2} \times \left(\frac{n}{2}+1\right) \times (n+1) }$

5. 결과적으로 아래와 같은 식으로 정리된다.
   $\boxed{ \frac{n(n+1)(n+2)}{6} }$