[TopCoder] InterestingDigits (Java, C#)

---

숫자 3과 9는 재미있는 성질이 있습니다. 3의 배수의 각 자릿수의 합은 다른 3의 배수가 됩니다.

예를 들어 118 * 3 = 354이고 3+5+4=12는 3의 배수입니다. 마찬가지로 9의 배수의 각 자릿수의 합은 다른 9의 배수가 됩니다.

예를 들어 75 * 9=675이고 6+7+5=18은 9의 배수입니다.

어떤 진법에서 이러한 성질을 갖는다고 다른 진법에서 이러한 성질을 가지지는 않습니다. 예를 들어 10진수에서 3은 이러한 성질을 가지지만 5진수에서는 성립하지 않습니다.

base 진법이 주어졌을 때 이러한 성질을 가진 수를 오름차순으로 모두 리턴하세요.(다만 0과 1은 제외합니다). 어떤 수가 이러한 성질을 가지는지 알고자 모든 숫자의 곱을 고려할 필요는 없습니다. 만약 4자리 미만의 곱으로 성립되면 더 큰 자리에서도 성립된다 할 수 있습니다.

예를 들어 10진수에서는 999보다 큰 숫자를 고려하지 않아도 됩니다.

---

 

문제 파악하기

1. 1000보다 작다 = 항상 세 자리수 이하
n진법에 맞게 계산을 할 때 각 자리 수에 n^(자리 수)를 곱해서 더하면 되는데, 세 자리수까지만 고려하면 되니까 간단하게 나타낼 수 있다.

2. n진법 수 % i == 0 && (각 자리수 합) % i == 0 인 수만 찾아야 한다.
모든 숫자가 저 조건을 만족하는 지 확인할 수도 있지만, 조건을 만족하지 않는 숫자를 발견하면 바로 break하고 다음 순번으로 넘어가는 것이 빠르다. 그렇기 때문에 n의 배수이지만 각 자리 수의 합이 n의 배수가 아니면 바로 break하기로 한다.

 

전체 코드는 아래와 같다.

(C#)

        private static int[] Solution(int baseNum)
        {
            List<int> answer = new List<int>();
            for (int i=2; i<baseNum; i++)
            {
               bool ok = true;
               for (int k1 = 0; k1 < baseNum; k1++)
                {
                    for (int k2 = 0; k2 < baseNum; k2++)
                    {
                        for (int k3 = 0; k3 < baseNum; k3++)
                        {
                            if((k1 + k2*baseNum +  k3*baseNum*baseNum) % i == 0 && (k1+k2+k3) % i != 0)
                            {
                                ok = false; break;
                            }
                        }
                        if (!ok) break;
                    }
                    if (!ok) break;
                }
               if (ok) answer.Add(i);
            }
            return answer.ToArray();
        }

 

 

(Java)

public class InterestingDigits {
	
	public int[] digits(int base) {
		
		ArrayList<Integer> answerList = new ArrayList<Integer>();
		
		for (int i=2; i<base; i++) {
			
			boolean pass = true;
			
			for (int k1=0; k1<base; k1++) {
				for (int k2=0; k2<base; k2++) {
					for (int k3=0; k3<base; k3++) {
						if((k1 + k2*base + k3*base*base)% i == 0){
						
							if ((k1 + k2 + k3)%i != 0) {
								pass = false;
								break;
							}
						}
						if (!pass) break;
					}
					if (!pass) break;
				}
				if (!pass) break;
			}
			if(pass) answerList.add(i);
		}
		
		//arraylist를 array로 변환
        int[] answer = new int[answerList.size()];
        for (int i = 0; i < answerList.size(); i++) {
            answer[i] = answerList.get(i);
        }
        
		
		return answer;
	}