[Topcoder] Interesting Digits(흥미로운 숫자)

  문제 설명(Definition)

---

숫자 3과 9는 흥미로운 속성을 공유합니다. 3의 배수를 취하여 숫자를 합하면 3의 배수가 됩니다. 예를 들어 118*3 = 354 및 3+5+4 = 3의 배수인 12입니다. 마찬가지로, 9의 배수를 선택하고 숫자를 합하면 9의 배수가 됩니다. 예를 들어 75*9 = 675 및 6+7+5 = 9의 배수인 18입니다. 이 속성이 중요한 숫자를 호출합니다. 0과 1은 속성이 사소한 값으로 고정합니다.

한 기저에 관심 있는 숫자가 다른 기저에 관심이 있는 것은 아니다. 예를 들어, 3은 10진수에서는 흥미롭지만 5진수에서는 흥미롭지 않습니다. 베이스가 지정되면 해당 베이스에 대한 모든 관심 있는 숫자를 증가하는 순서로 반환하는 것이 작업입니다. 특정 숫자가 흥미로운지 여부를 확인하기 위해 숫자의 모든 배수를 고려할 필요는 없습니다. 속성이 4자리 미만의 모든 자릿수에 대해 유지되는 경우에는 더 많은 자릿수에 대해서도 유지됩니다. 예를 들어, 기저 10에서 999보다 큰 배수는 고려할 필요가 없습니다.

Definition

Class:

 

InterestingDigits

Method:

 

digits

Parameters:

 

int

Returns:

 

vector <int>

Method signature:

 

vector <int> digits(int base)

 

Examples

0)

10

Returns: { 3, 9 }

All other candidate digits fail for base=10. For example, 2 and 5 both fail on 100, for which 1+0+0=1. Similarly, 4 and 8 both fail on 216, for which 2+1+6=9, and 6 and 7 both fail for 126, for which 1+2+6=9.

1)

3

Returns: { 2 }

2)

9

Returns: { 2, 4, 8 }

3)

26

Returns: { 5, 25 }

4)

30

Returns: { 29 }

 

  문제 풀이(Solution)

---

범위를 3자리 수 이하로 제한하였으므로, 전체 탐색을 이용한다. 

 

#include <vector>
using namespace std;

class InterestingDigits
{
public:
    vector <int> digits(int base)
    {
        vector <int> ans;
        
        for(int n=2; n<base; n++)
        {
            bool ok = true;
            
            for(int k1=0; k1<base; k1++)
            {
                for(int k2=0; k2<base; k2++)
                {
                    for(int k3=0; k3<base; k3++)
                    {
                        int number = k1 + k2*base + k3*base*base;
                        int each_sum = k1 + k2 + k3;
                        if(number%n == 0 && each_sum%n != 0)
                        {
                            ok = false;
                            break;
                        }
                    }
                    if(!ok) break;
                }
                if(!ok) break;
            }
            if(ok) ans.push_back(n);
        }
        return ans;
    }
};

N진수가 주어졌을 때, 우리는 조건을 만족하는 수를 전부 찾아야한다. 

 

문제에서 주어진 예시에서 10진수 상황에서는 3과 9가 그 조건을 만족했다. 

vector <int> ans;

반환값이 vector <int>이므로 이 벡터에 만족하는 수들을 넣어준다. 

for(int n=2; n<base; n++)

base진법의 base 이하의 수를 모두 순회한다. 이 중에 정답이 존재한다. 

            for(int k1=0; k1<base; k1++)
            {
                for(int k2=0; k2<base; k2++)
                {
                    for(int k3=0; k3<base; k3++)

base진법의 세자리 수 이하의 모든 수를 순회(탐색)한다.

                        int number = k1 + k2*base + k3*base*base;
                        int each_sum = k1 + k2 + k3;
                        if(number%n == 0 && each_sum%n != 0)
                        {
                            ok = false;
                            break;
                        }

각 case마다 각 자리수 합을 계산하고 조건을 통과시킨다.

if(number%n == 0 && each_sum%n != 0)

핵심인 조건문인데 케이스가 찾고자 하는 n의 배수이면서 각 자리수 합이 n의 배수가 아니라면 

 

k1, k2, k3 반복문을 차례로 break한다. 왜냐하면 한 케이스라도 조건에 어긋나면 답이 아니다. 

if(ok) ans.push_back(n);

3자리수의 모든 범위를 탐색한 이후에도 ok가 false로 바뀌지 않았다면 n은 내가 찾고자하는 답이다. 

 

이를 ans 벡터에 넣어준다. 

return ans;

최종적으로 이를 반환한다.