https://www.acmicpc.net/problem/1664



일단 올려놓고 계속 풀긴할건데, 여러분들 아이디어가 궁금해서요.

저는 c의 유무에 따라서 풀고있는데

c가 없을 때는 구할 수 있는뎅


문제가 c가 있을때네요. 

c가 없을 때 풀듯이하면 한번씩 다 검사를 해줘야하기때문에, 무조건 타임아웃이 나오고

지금 생각한거론

c가 나올 수 있는 값 = (19*X) + C이니까, D~A까지의 최댓값 내에서 반복해서 값을 찾는건데..


너무 복잡하고, 아프네요 지금 1시간 30분째 생각하고있는데 ㅋㅋㅋㅋ

문제

내일이면 대한민국에 새로운 대통령이 취임하게 된다. 새로운 정부는, 아래와 같이 19자리로 된 새로운 주민등록번호 체계를 도입한다고 한다.

DDMMYYYYAAAAAAAAAAC

YYYY는 생년, MM은 생월, DD는 생일을 의미한다. 생년은 0001 이상 9999 이하의 수가 되며, MM은 01 이상 12 이하, DD는 01 이상 31 이하이다. 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지이며, 2월은 평년은 28일까지, 윤년은 29일까지이다. 윤년이란 YYYY가 (1) 100의 배수를 제외한 4의 배수이거나 (2) 400의 배수인 경우가 해당된다.

A로 된 10자리는 어떤 숫자라도 올 수 있다. 마지막 자리인 C는 CONTROL-DIGIT으로, 아래와 같은 알고리즘에 의해 생성된다.

  1. C를 제외한 주민등록번호상의 18자리의 수를 순서대로 Z1, Z2, …, Z18이라고 하자.
  2. S = (10×Z1 + 9×Z2 + 8×Z3 + … + 2×Z9 + 10×Z10 + 9×Z11 + 8×Z12 + … + 2×Z18)
  3. S가 9 이하이면 C=S, 아니면 C = 19 - S

이러한 새로운 주민등록번호 체계상의 한 주민등록번호의 일부 숫자가 지워져 있다. 위의 조건을 만족시키는 가능한 모든 주민등록번호의 경우의 수를 세는 프로그램을 작성하시오.

입력

첫째 줄에 19자리의 주민등록번호가 주어진다. 숫자 또는 X로 주어지게 되는데 X는 숫자가 지워졌음을 의미한다.

출력

첫째 줄에 조건을 만족시키는 가능한 모든 주민등록번호의 경우의 수를 출력한다. 답은 항상 2^63보다 작다.

예제 입력 1 <button type="button" class="btn btn-link copy-button" data-clipboard-target="#sample-input-1" style="line-height: 1.42857; font-size: 14px; cursor: pointer; color: rgb(66, 139, 202); border-width: 1px; border-style: solid; border-color: transparent; text-align: center; border-radius: 0px; font-style: inherit; font-variant: inherit; font-stretch: inherit; overflow: visible; white-space: nowrap; vertical-align: middle; user-select: none; background-image: none; box-shadow: none; font-family: "Open Sans", "Apple SD Gothic Neo", "Noto Sans CJK KR", "Noto Sans KR", 나눔바른고딕, 나눔고딕, 맑은고딕, "Helvetica Neue", Helvetica, Arial, sans-serif !important; outline: 0px !important;">복사</button>
XX0220051234567890X
예제 출력 1 <button type="button" class="btn btn-link copy-button" data-clipboard-target="#sample-output-1" style="line-height: 1.42857; font-size: 14px; cursor: pointer; color: rgb(66, 139, 202); border-width: 1px; border-style: solid; border-color: transparent; text-align: center; border-radius: 0px; font-style: inherit; font-variant: inherit; font-stretch: inherit; overflow: visible; white-space: nowrap; vertical-align: middle; user-select: none; background-image: none; box-shadow: none; font-family: "Open Sans", "Apple SD Gothic Neo", "Noto Sans CJK KR", "Noto Sans KR", 나눔바른고딕, 나눔고딕, 맑은고딕, "Helvetica Neue", Helvetica, Arial, sans-serif !important; outline: 0px !important;">복사</button>
28