문제에서 최소 생성자를 찾아야하는데, 분해합이 N이 최대 1,000,000까지 주어지는데 0부터 찾으면 오래걸릴 것 같아서 6자리므로 최대 54쯤 나오겠지 싶어서 N-60부터 찾았다.
그런데 자리수 합 45의 수 999999의 분해합이 상한을 넘는다. 6자리의 각 자리수 합이 53이려면 9 5개, 8 1개로 구성된 수 인데,
899999 989999 998999 999899 / 999989 999998 900052 990052 999052 999952 /1000042 1000051 범위 내의 앞 4개의 수가 테스트케이스에 있었다고 생각할 수 있다. 최대 6자리 수 분해합부터 다룰 때는 N-53부터 찾으면 제일 빠르겠다.
tpdnb4me 2년 전 1
문제에서 최소 생성자를 찾아야하는데, 분해합이 N이 최대 1,000,000까지 주어지는데 0부터 찾으면 오래걸릴 것 같아서 6자리므로 최대 54쯤 나오겠지 싶어서 N-60부터 찾았다.
그런데 자리수 합 45의 수 999999의 분해합이 상한을 넘는다. 6자리의 각 자리수 합이 53이려면 9 5개, 8 1개로 구성된 수 인데,
899999 989999 998999 999899 / 999989 999998900052 990052 999052 999952 /1000042 1000051
범위 내의 앞 4개의 수가 테스트케이스에 있었다고 생각할 수 있다. 최대 6자리 수 분해합부터 다룰 때는 N-53부터 찾으면 제일 빠르겠다.
앞으로 풀 브루트포스 문제 시작점을 정하는데 도움이 되지 않을까?
...
아님 말고... 솔직히 궁금했잔아...