codewars: A Rule of Divisibility by 13

문제 링크입니다: https://www.codewars.com/kata/564057bc348c7200bd0000ff/train/cpp

재귀를 이용하면 상당히 쉽게 풀 수 있는 문제입니다.

/*

배열이 다음과 같이 주어졌다고 하자 {1, 2, 3, 4, 3, 2, 1};

3번째 index를 기준으로 왼쪽과 오른쪽의 합이 6으로 같기 때문에

당신의 함수는 3을 반환해야한다.

다른 예시로는 {1, 100, 50, -51, 1, 1};이 있다.

1번째 index를 기준으로 왼쪽과 오른쪽의 합이 1로 같기 때문에

당신의 함수는 1을 반환해야한다.

*/

#include <vector>

#include <iostream>

using namespace std;

 

//배열이 정렬이 되어있다면 binary search로 풀었겠지만

//정렬을 할 수 없기 떄문에 무식하게 풀었다.

int find_even_index(const vector<int> numbers)

{

        for (int i = 0; i < numbers.size(); i++)

        {

               int leftSum = 0, rightSum = 0;

               if (i == 0)

                       leftSum = 0;

               for (int j = 0; j < i; j++)

                       leftSum += numbers[j];

               for (int j = i+1; j/*

10^0부터 10^5까지 13으로 나누면

나머지가 1, 10, 9, 12, 3, 4이다.

10^6부터는 13으로 나누었을 때 위의 순서를 반복한다.

 

다음과 같이 작동하는 함수를 작성한다:

숫자가 주어졌을 때 1의 자리숫자와 10^0을 13으로 나눈 숫자를 곱하고

10의 자리숫자와 10^1을 13으로 나눈 숫자를 곱한 것을 더하고

100의 자리숫자와 10^2을 13으로 나눈 숫자를 곱한 것을 더하고

... 이런식으로 더한다.

 

예시: 1234567이 주어졌을 때

7×1 + 6×10 + 5×9 + 4×12 + 3×3 + 2×4 + 1×1 = 178

 

178에서 또 다시 반복한다

8x1 + 7x10 + 1x9 = 87

 

87에서 또 다시 반복한다

7x1 + 8x10 = 87

 

이렇게 전에 구한 합과 합이 동일할 경우 합을 반환하는 함수를 작성하시오

*/

#include <iostream>

using namespace std;

 

long long divisions[6] = { 1, 10, 9, 12, 3, 4 }; //10^0~10^5를 13으로 나눈 나머지

long long save = 0; //전에 구한 합을 저장하기 위해

 

//저번과 마찬가지로 굳이 class를 선언할 필요가 있나 싶다.

class Thirteen

{

public:

        static long long thirt(long long n);

};

 

long long Thirteen::thirt(long long n)

{

        long long sum = 0; //합

        //cnt는 몇번째 나머지를 곱해야할지 판별하기 위해, length는 자릿수 구하기용

        int cnt = 0, length = 0;

        long long temp = n; //자릿수를 구하기 위해 n을 복사

        while (temp>0) //자릿수를 구하고

        {

               temp /= 10;

               length++;

        }

        for (int i = 0; i < length; i++) //자릿수만큼 반복

        {

               long long digit = n % 10; //현재 제일 낮은 자릿수 구하고

               sum += digit*divisions[cnt]; //곱한다

               n -= digit;

               n /= 10; //제일 낮은 자릿수 삭제

               cnt++;

               if (cnt == 6) //6번마다 반복하므로

                       cnt = 0;

        }

        if (save == sum) //저번 합과 같으면 반환

               return sum;

        save = sum; //save를 업데이트 하고

        return thirt(sum); //재귀

}

 

int main(void)

{

        cout << Thirteen::thirt(8529) << endl;

        cout << Thirteen::thirt(85299258) << endl;

        cout << Thirteen::thirt(5634) << endl;

        cout << Thirteen::thirt(1111111111) << endl;

        cout << Thirteen::thirt(987654321) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~