완전 좌우 대칭인 시간 찾는 문제

2015-01-11 10:51:02

2015-01-22 10:51:02

2015-02-11 20:51:02

2015-02-22 20:51:02

2015-10-11 01:51:02

2015-10-22 01:51:02

2015-11-11 11:51:02

2015-11-22 11:51:02

2015-12-11 21:51:02

2015-12-22 21:51:02

위와 같이 14개 숫자로 이루어진 시간이

앞 7개 뒷 7개가 대칭을 이루는 시간을 완전 좌우 대칭인 시간이라고 할때

1970-01-01 00:00:00 부터 9999-12-31 23:59:59 까지 시간중에

완전 대칭인 시간은 몇개가 있을까?

14개 숫자가 0~9까지 가능하다고 할때 체크해봐야 하는 경우의 수는 10의 14승

즉 100,000,000,000,000=백만*억개이다.

경우의 수가 너무 많으므로 이걸 줄여보자.

좌우 대칭이라는 말을 잘 생각해 보면 결국 같은 숫자가 2개씩 짝을 이루어 나온다는 말이다.

앞자리부터 알파벳으로 표시해보자면

ABCD-EF-GG FE:DC:BA

결국 ABCDEFG|GFEDCBA

사실 구해야 하는 숫자는 A~G 7개뿐인 것이다.

경우의 수가 10,000,000=천만개로 줄었다.

하지만 이건 대칭인 숫자를 찾는 경우의 수고.

여기선 시간을 찾는 것이기 때문에 제약사항이 더 존재한다.

즉 초는 59초를 넘을 수 없다. 월은 12월을 넘을 수 없고 0월은 없다. 같은 제약들이다.

또한 한 쌍을 이루기 때문에 한 쌍의 각각의 제약사항이 동시에 적용된다.

그러면 ABCDEFG가 가능한 범위를 하나씩 확정해보자.

-A,B

A는 몇천년에 해당하고 B는 몇백년에 해당한다.

그리고 BA는 몇십몇초이다.

A는 1970년 이후의 시간을 찾는것이니 최소 1이상이어야 한다. A:1~9

B는 십초이니 5를 넘을 수 없다. 즉 6이상이 아니다. B:0~5

이때 A가 1이면 B의 범위에 따라 1000년~1500년이 되버리므로

1970년 이후라는 제약 사항에 만족하지 못한다.

따라서 A가 1인 경우는 배제해야 한다. 결국 A는 2 이상이 된다.

A:2~9

B:0~5

-C,D

CD는 몇십몇년에 해당하고 DC는 몇십몇분에 해당한다.

위에서 A의 범위가 2이상이므로 1900년대가 아예 배제되었으므로

1900년대에 70년 이후라는 제약사항은 고려할 필요가 없어졌다.

하지만 D의 제약사항은 몇십분. B의 경우와 같이 6이상이 되지 못한다.

다른 별다른 제약사항은 없는듯 하다.

C:0~9

D:0~5

-E,F

EF는 몇십몇월이고 FE는 몇십시몇분이다.

이때 E는 20월은 없으니 0~1이 된다.

F는 몇십시이므로 24시간 범위를 맞추려면 0~2가 된다.

하지만 F는 E가 0일때는 00월은 없으니 E가 0일때는 1~2로 줄어든다.

E: 0~1

F(E=0) :1~2

F(E=1) :0~2

-G

GG는 몇십몇일이다.

즉 한달에 두자리 수가 반복되는 날은 11일 22일 밖에 되지 않는다.

G: 1~2

결국

A:2~9    8개

B:0~5    6개

C:0~9    10개

D:0~5    6개

E: 0~1    2개

F(E=0) :1~2    2개

F(E=1) :0~2    3개

G: 1~2    2개

이다.

E가 0일때 경우의 수는 E를 빼고 가짓수를 곱하여 얻을 수 있다.

즉 8*6*10*6*2*2=11520

E가 1일때 경우의 수는

8*6*10*6*3*2=17280

두 경우의 수를 합치면 28800개가 나온다.

즉 1970-01-01 00:00:00 부터 9999-12-31 23:59:59 까지 시간중에

완전 대칭인 시간은 28,800개가 있다.

2만8천8백개 밖에 되지 않으니 간단한 코드로 이 모든 14글자의 조합을 얻을 수 있다.

char symTime[28800][7];

int A, B, C, D, E, F, G;

int idx = 0;

for (A = 2; A <= 9; A++) { //A

 for (B = 0; B <= 5; B++)  //B

  for (C = 0; C <= 9; C++)  //C

   for (D = 0; D <= 5; D++)  //D

    for (E = 0; E <= 1; E++)  //E

     for (F = 0; F <= 2; F++) {  //F

         if (E == 0 && F == 0)

             continue;

         for (G = 1; G <= 2; G++) { //G

             symTime[idx][0] = A + 48;

             symTime[idx][1] = B + 48;

             symTime[idx][2] = C + 48;

             symTime[idx][3] = D + 48;

             symTime[idx][4] = E + 48;

             symTime[idx][5] = F + 48;

             symTime[idx][6] = G + 48;

             idx++;

         }

     }

}

출력시 [0]~[6],[6]~[0] 형식으로 출력해주면 된다.