028. Number Spiral Diagonals [소용돌이 회전수에서 대각선에 있는 수의 합 구하기]

​문제 (English)

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

 It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

문제 분석

---

격자에서 소용돌이 모양으로 회전하며 숫자를 증가시키면서 배치할 때, 대각선에 놓이게 되는 숫자들의 합을 구하는 문제.

 

수열 문제이다. 규칙을 찾아서 $i$가 증가할 때마다의 대각선에 놓일 수를 예측할 수 있다면, 그 수들을 더하면 된다.

 

그런데, 이게 1001 by 1001 정도면 루프를 돌면서 합을 구하면 되겠지만, $10^9$ by $10^9$ 정도를 넘어가게 되면, 루프로 풀기가 어렵다. 더군다나 hackerrank의 문제에서처럼 $10^{18}$ by $10^{18}$에 대한 문제면 루프를 돌면서 구할 수는 없다. 

이러한 경우는, 수열에 대한 합 공식을 이용해서 합에 대한 수식을 만들고, 그것을 이용해서 풀어야 한다. 

 

풀이 1 

---

루프를 통해서 수열값을 생성하고, 그 값을 더해나가는 형태로 풀어보자.

 

먼저, 규칙을 찾아야겠다. 

엑셀로 9 by 9 짜리 소용돌이 수를 그려봤다.

음영 표시된 부분의 합을 구하는 것이다.

 

순서대로 보면 (1), (3,5,7,9), (13,17,21,25), ... 형태이다. 뭔가 규칙성이 있다.

t=1:  (1)

t=3:  (3,5,7,9) --> 2씩 증가

t=5: (13,17,21,25) --> 4씩 증가

t=7: (31,37,43,49) --> 8씩 증가

 

t=5이면, 맨처음 있는 1을 제외하고, 루프를 2번 돌면서 더하면 되겠다. 

루프 변수 i를 두고, 첫 번째 루프에서는 i=2로 해서 (3,5,7,9)를 처리, 두 번째 루프에서는 i=4로 되게 해서 (13,17,21,25)를 처리하면 되겠다.

#[test]
fn test(){
    assert_eq!(25, answer(3)); // (3,5,7,9)
    assert_eq!(101, answer(5));// + ()
    assert_eq!(669171001, answer(1001));    
}

fn answer(n:usize) -> usize {
    let mut i = 0;
    let mut sum = 1;
    let mut k = 1;
    while i < (n-1) {
        i += 2;
        for _ in 0..4 {
            k += i;
            sum += k;
        }
    }
    return sum;
}

 

풀이 2 

---

풀이 1로는 대략 $10^9$ by $10^9$ 정도 이상의 문제에 대해서 풀기 힘들다. 시간도 오래 걸리고, u64나 u128로도 합 값을 표현하기 힘들다. 

hackerrank에서 주어진 문제가 그러한데, 무려 $10^{18}$ by $10^{18}$ 정도 되는 문제를 풀어야 한다. 답을 낼 때는 $10^9+7$로 모듈레이션 해서 출력하게 되어 있다.

 

이렇게 큰 수에 대해서는 루프를 돌면서 합을 구할 수 없다. 

수열의 규칙성을 찾아서 수열식을 만들고, 이 수열식에서 합을 구하는 수식을 만들어내서 풀어야 한다.

 

먼저, 수열식의 규칙을 찾아야겠다. 

음영 표시된 부분의 합을 구하는 것이다.

 

순서대로 보면 (1), (3,5,7,9), (13,17,21,25), ... 형태이다. 뭔가 규칙성이 있다. 4개씩 그룹으로 움직인다. 

이런 경우 하나의 수열식의 규칙성을 찾기보단, 분리해서 생각하는 게 좋다. 

대각선을 4개로 나눠서 생각해 보자. 

n = {1,2,3,...}라고 할 때,

A 그룹: (9,25,49,...)  --> $A(n) = (2n+1)^{2} = 4n^2+4n+1 $

B 그룹: (7,21,43,...) --> $B(n) = A(n) - 2n = 4n^2 + 2n + 1$

C 그룹: (5,17,37,...) --> $C(n) = B(n) - 2n = 4n^2 + 1$

D 그룹: (3,13,31,...) --> $D(n) = C(n) - 2n = 4n^2 -2n + 1$

 

위 그룹에서 제일 가운데 있는 1이 빠져 있다. 해서, 전체 합은 이 1과 A, B, C, D에 대해 모두 더하면 된다. 

즉, n={1,2,3...}일 때

$$ S(n) = 1 + \sum_{k=1}^{n}{\left(A(k) + B(k) + C(k) + D(k)\right)} = 1 + \sum_{k=1}^{n}{\left(16k^{2} + 4k + 4  \right)}$$

$$ = 1 + 16\sum_{k=1}^{n}{k^2} + 4\sum_{k=1}^{n}{k} + 4n \tag{1}$$

 

합의 공식은,

$$ \sum_{k=1}^{n}{k^2} = \frac {n(n+1)(2n+1)}{6}$$

$$ \sum_{k=1}^{n}{k} = \frac {n(n+1)}{2}$$

 

합의 공식을 식(1)에 적용하면,

$$ S(n) = 1 + 16\left\{ \frac {n(n+1)(2n+1)}{6}\right\} + 4\left\{ \frac{n(n+1)}{2} \right\} + 4n $$

$$ = 1+ \frac{8}{3}(2n^3+3n^2+n) + (2n^2+2n) + 4n = 1+\frac{16}{3}n^3+10n^2+\frac{26}{3}n $$

$$ = 1+\frac{2n}{3} (8n^2+15n+13) \tag {2}$$

 

식(2)는 n={1,2,3,4}일 때이다. 예를 들어 n=1이면 3 by 3에 대한 합이다. 

따라서, 문제에서 3 by 3에 대한 합을 구하라면 S(1)을 구해야 하고, 5 by 5에 대한 합은 S(2)이다.

따라서, 3 by 3에 대한 합을 구할 때, n=3으로 주어졌다면, 이것을 n=(n-1)/2로 바꾼 후 S(n)을 구하면 되겠다.

fn answer1(mut n:u128) -> u128 {    
    n = (n - 1) / 2;    
    let ans = 2 * n * (8 * n * n + 15 * n + 13) / 3 + 1;
    return ans;
}

 

위 코드는 hackerrank에서 요구한 $10^9+7$로 모듈레이션을 하라는 조건이 빠져 있다. 이를 반영하면,

fn answer2(mut n:u128) -> u128 {
    let m = 1000000000 + 7;
    
    n = (n - 1) / 2;
    n = n % m;
    let ans = 2 * n * (8 * n * n + 15 * n + 13) / 3 + 1;
    return ans % m;
}

 

총평

---

수열의 규칙성을 찾고, 이를 코드로 구현하는 문제이다.

프로그래매틱하게는, 루프를 돌면서 수열의 다음값을 찾아서 이를 더해나가는 것이 일반적인 방법이겠다.

 

그러나, 수열의 크기가 너무 클 때($10^9$ 이상)는, 루프를 돌아서는 시간이 너무 걸린다.

 

이경우는, 어떻게든 합을 구하는 식을 유도해 내서 푸는 수밖에 없겠다.

 

이 문제는 이러한 연습을 하게 하는 문제.

 

전체 소스코드

---

p28.rs 

use std::u128;

#[test]
fn test(){
    assert_eq!(25, answer(3)); // (3,5,7,9)
    assert_eq!(101, answer(5));// + ()
    assert_eq!(669171001, answer(1001));    
}

#[cfg(test)]
fn answer(n:usize) -> usize {
    let mut i = 0;
    let mut sum = 1;
    let mut k = 1;
    while i < (n-1) {
        i += 2;
        for _ in 0..4 {
            k += i;
            sum += k;
        }
    }
    return sum;
}

//-----------------------
//hackerrank
#[test]
fn test1(){
    assert_eq!(25, answer1(3)); // (3,5,7,9)
    assert_eq!(101, answer1(5));// + ()
    assert_eq!(669171001, answer1(1001));    
    
    assert_eq!(78073657, answer2(10e18 as u128 - 1));    
}

#[cfg(test)]
fn answer1(mut n:u128) -> u128 {    
    n = (n - 1) / 2;    
    let ans = 2 * n * (8 * n * n + 15 * n + 13) / 3 + 1;
    return ans;
}

#[cfg(test)]
fn answer2(mut n:u128) -> u128 {
    let m = 1000000000 + 7;
    
    n = (n - 1) / 2;
    n = n % m;
    let ans = 2 * n * (8 * n * n + 15 * n + 13) / 3 + 1;
    return ans % m;
}

 

끝