Perimeter of squares in a rectangle

The drawing shows 6 squares the sides of which have a length of 1, 1, 2, 3, 5, 8. It's easy to see that the sum of the perimeters of these squares is : 4 * (1 + 1 + 2 + 3 + 5 + 8) = 4 * 20 = 80

Could you give the sum of the perimeters of all the squares in a rectangle when there are n + 1 squares disposed in the same manner as in the drawing:

 

Hint:

See Fibonacci sequence

 

Ref:

http://oeis.org/A000045

 

The function perimeter has for parameter n where n + 1 is the number of squares (they are numbered from 0 to n) and returns the total perimeter of all the squares.

perimeter(5)  should return 80 perimeter(7)  should return 216

 

solution

#include <iostream>

typedef unsigned long long ull;
class SumFct
{
public:
  static ull perimeter(ull n);
  static ull fibo(const ull& k, const ull& l, const ull& m, const ull& n, ull& r);
};

ull SumFct::fibo(const ull& k, const ull& l, const ull& m, const ull& n, ull& r) {
  if (k < l) return r;
  r += m;
  return fibo(k, l + 1, n, m + n, r);
}

ull SumFct::perimeter(ull n) {
  ull r = 0;
  return 4 * fibo(n, 0, 1, 1, r);
}

 

pva의 코드

typedef unsigned long long ull;
class SumFct {
 public:
  static ull perimeter(int n) {
    ull n0 = 1;
    ull n1 = 1;
    ull result = n == 0 ? 1 : 2;
    for (int i = 2; i <= n; i++) {
      n1 = n0 + n1;
      n0 = n1 - n0;
      result += n1;
    }
    return result * 4;
  }
};

 

후기

이 문제를 풀면서 많은 고민을 했다. 대체 나는 왜 기본 중의 기본인 피보나치수열조차도 풀어내지 못하는 것일까? 스스로가 너무나도 답답했다. 하지만! 피보나치수열을 못 풀어내는 것이 아니라 둘레의 길이를 구하지 못했던 것이다. 정사각형의 둘레의 길이를 구하려면 4를 곱해야 하는데 그걸 못 잡아내서 시간을 보냈다. 만약 이게 실전 테스트였다면 흘러가는 1분 1초가 너무나도 야속했을 뻔했다. 다행히도 실전은 아니었고.

다른 사람들의 설루션을 봤을 때는 놀라웠다. 과연 이렇게도 저렇게도 풀 수 있는 문제였구나. 나는 단지 힌트에 써져있었던 피보나치수열을 사용해야만 한다는 고정관념이 생겼던 것 같다. 그 속에서도 피보나치수열은 재귀 함수로만 풀어야 한다는. 힌트가 없으면 완전 자유라서 힘들지만, 힌트는 틀을 만들어서 그 틀에 갇히게 만든다는 생각도 든다. Cheer up

 

(url: https://www.codewars.com/kata/559a28007caad2ac4e000083)