[Codewars] [7Kyu] Sum of odd numbers

Codewars: Achieve mastery through challenge

이번 문제는 연속된 홀수 값들을 피라미드로 만들고, 그 피라미드의 층(row)에 대한 값을 구해서 반환하는 문제입니다.

문제에서 주어지는 형태

위의 이미지처럼 계속 되는 수들의 해당 층의 값을 구하면 됩니다.

 

1. Swift

1-1. 본인의 풀이

먼저 규칙성을 찾아봅시다.

row : 1 = 1

row : 2 = 3 + 5 = 8

row : 3 = 7 + 9 + 11 = 27

...

보면 row의 3제곱이 결과값이 되는 것을 알 수 있습니다.

이건 일단 단순한 계산이고, 좀 더 수학적으로 접근하면 다음과 같습니다.

 

m번째 홀수 숫자를 구하는 공식은 2m - 1이 됩니다.

n열까지의 전체 숫자의 갯수를 구해보면 n * (n + 1) / 2가 됩니다.(a)

n = 1 -> 1, n = 2 ->3, n = 3 -> 6, ...

그리고 각 열의 맨 처음 숫자는 n * (n + 1) / 2 - (n - 1) == (n - 1) * n / 2 + 1 입니다.(b)

n = 1 -> 1, n = 2 -> 2, n = 3 -> 4

그럼 각 열의 시작과 끝 홀수 숫자들은 다음과 같이 정의가 됩니다.

2(b) - 1 ~ 2(a) - 1까지의 홀수 숫자.

각 숫자의 합은 다음과 같이 구할 수 있습니다

(시작 + 끝) * 갯수 / 2

즉, (2(b) - 1 + 2(a) - 1) * n / 2입니다.

수식을 풀어보면 (2( (n-1)*n/2 + 1 ) - 1 + 2( n*(n+1)/2 ) - 1) * n / 2가 됩니다.

각 항을 풀어주면 ((n-1)*n + 2 - 1 + n*(n+1) - 1) * n / 2 == (n^2 - n + 2 - 1 + n^2 + n - 1) * n / 2가 됩니다.

다시 한 번 풀어주면 결과는 n^3이 나옵니다.

func rowSumOddNumbers(_ row: Int) -> Int {
  return row * row * row
}

따라서 위의 코드가 나옵니다.

 

이것 말고 재밌는 풀이 방식이 있는데

1^2 - 0 = > 1^2 * 1 == 1^2 - (0^0은 본디 정의되지 않는 수이기 때문에 무시한다고 판단. 즉 0으로 일단 계산) // 1 - 0 = 1

2^2 - 1 ,  2^2 + 1 = >2^2 * 2 == 3 ^ 2 - 1^1 // 9 - 1 = 8

3^2 - 2, 3^2 + 0, 3^2 + 2 => 3^2 * 3 == 6 ^ 2 - (3 ^ 2) // 36 - 9 = 27

4^2 - 3, 4^2 - 1, 4^2 + 1, 4^2 + 3 => 4^2 * 4 == 10 ^ 2 - (6 ^ 2) // 100 - 36 = 64

5^5 - 4, 5^2 - 2, 5^2, 5^2 + 2, 5^2 + 4 => 5^2 * 5 == 15 ^ 2 - (10 ^ 2) // 225 - 100 = 125

...

이런 식으로 값을 구할 수도 있는 것 같습니다.(끄적이다보니 나오네요)

(검증은 안했어요...규칙성만 있는 것 같아서 일단 보류)

 

이번 문제는 규칙만 찾으면 쉽다보니 풀이가 비슷하네요.