[Project Euler] 43. 부분열에 관련된 특이한 성질을 가진 모든 팬디지털 숫자의 합

43. 부분열에 관련된 특이한 성질을 가진 모든 팬디지털 숫자의 합

숫자 1406357289은 0 ~ 9 팬디지털인데, 부분열에 관련된 재미있는 성질을 가지고 있습니다.

d1을 첫째 자리수, d2를 둘째 자리수...라고 했을 때, 다음과 같은 사실을 발견할 수 있습니다.

d2 d3 d4 = 406 → 2로 나누어 떨어짐
d3 d4 d5 = 063 → 3으로 나누어 떨어짐
d4 d5 d6 = 635 → 5로 나누어 떨어짐
d5 d6 d7 = 357 → 7로 나누어 떨어짐
d6 d7 d8 = 572 → 11로 나누어 떨어짐
d7 d8 d9 = 728 → 13으로 나누어 떨어짐
d8 d9 d10 = 289 → 17로 나누어 떨어짐

위와 같은 성질을 갖는 0 ~ 9 팬디지털을 모두 찾아서 그 합을 구하면 얼마입니까?

Click  

그야말로 값들을 하나하나 넣을때마다 조건을 따져가며 10개의 자릿수를 채워 팬디지털을 만들는 과정을 거치는게 가장 빠를 것입니다.  그전에 수의 성질을 몇가지 이용하면 위의 조건 중 몇가지를 수정할 수 있습니다.

d2 d3 d4 = 406 → 2로 나누어 떨어짐 → d4 = 짝수
d3 d4 d5 = 063 → 3으로 나누어 떨어짐 → d3 + d4 + d5 = 3으로 나누어 떨어짐.
d4 d5 d6 = 635 → 5로 나누어 떨어짐 → d6 = 0 or 5
d5 d6 d7 = 357 → 7로 나누어 떨어짐
d6 d7 d8 = 572 → 11로 나누어 떨어짐
d7 d8 d9 = 728 → 13으로 나누어 떨어짐
d8 d9 d10 = 289 → 17로 나누어 떨어짐

이제 d1부터 하나씩 구해가면서 위에 조건과 만족하는 결과를 배치해 가며 구합니다.

d1,d2는 그 어떤 성질에도 영향을 주지 않으니 0~9의 수에서 서로 겹치지 않게 배치.
d3는 2번째 성질에 영향을 주지만 시작점이니 역시 0~9의 수에서 d1,d2와 겹치지 않게 배치.
d4는 짝수 중에서 앞의 값들과 겹치지 않게 배치.
d5는 (3-(d3+d4))%3 값을 시작으로 3씩 더해가면서 앞에서 구한 값들과 겹치지 않게 배치.
d6는 0,5 중에서 앞의 값과 겹치지 않게 배치.
d7은 (7-((d5*100+d6*10)%7))%7과 7을 더해서 9가 넘지 않는 수를 앞에서 구한 값들과 겹치지 않게 배치.
d8은 (11-((d6*100+d7*10)%11))%11 이 앞에 구한 값과 겹치지 않고 9이하라면 배치.
d9는 (13-((d7*100+d8*10)%13))%13 이 앞에 구한 값과 겹치지 않고 9이하라면 배치.
d10은 (17-((d8*100+d9*10)%17))%17 이 앞에 구한 값과 겹치지 않고 9이하라면 배치.

<script language="Javascript" type="text/javascript">
function p043(){
  var r = 0, check = [true,true,true,true,true,true,true,true,true,true];
  for(var d1=0; d1<10; d1++){
    check[d1] = false;
    for(var d2=0; d2<10; d2++) if(check[d2]){
      check[d2] = false;
      for(var d3=0; d3<10; d3++) if(check[d3]){
        check[d3] = false;
        for(var d4=0; d4<10; d4+=2) if(check[d4]){
          check[d4] = false;
          for(var d5=(3-((d3+d4)%3))%3; d5<10; d5+=3) if(check[d5]){
            check[d5] = false;
            for(var d6=0; d6<10; d6+=5) if(check[d6]){
              check[d6] = false;
              for(var d7=(7-((d5*100+d6*10)%7))%7; d7<10; d7+=7) if(check[d7]){
                check[d7] = false
                var d8=(11-((d6*100+d7*10)%11))%11;
                if(d8<10 && check[d8]){
                  check[d8] = false;
                  var d9 = (13-((d7*100+d8*10)%13))%13;
                  if(d9<10 && check[d9]){
                    check[d9] = false;
                    var d10 = (17-((d8*100+d9*10)%17))%17;
                    if(d10<10 && check[d10])
                      r += d1*1000000000+d2*100000000+d3*10000000+d4*1000000+
                           d5*100000+d6*10000+d7*1000+d8*100+d9*10+d10;
                    check[d9] = true;
                  }
                  check[d8] = true;
                }
                check[d7] = true;
              }
              check[d6] = true;
            }
            check[d5] = true;
          }
          check[d4] = true;
        }
        check[d3] = true;
      }
      check[d2] = true;
    }
    check[d1] = true;
  }
  alert(r);
}
</script>