[질문] 요 문제 힌트좀 주십셔 ㅠ

[익명(110.70)]

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

갤주형님이 어제 프갤에 뿌리고 간 뒤로 고민해봤는데

뭘로 풀어야 하는지 모르겠슴당

[익명(218.54)]

digit sum arithmetic

[익명(218.54)]

아니다 문제 잘못 봄 ㅎ

[익명(175.223)]

[메리체리(mrscherry)]

킹갓아이디어를 생각하면됨

[익명(39.7)]

[ㅅㅅ(59.152)]

숫자에서 각 자리수가 중요하니까 자리수를 쪼개서 생각해보셈.숫자에 x가 곱해지면 각 자리수에도 x가 곱해지겠죠?각 자리 수를 a[i]라고 하면 결국 (x배에 대한 자리수의 합 % 2)는 sum(sum_of_digit(a[i]*x)) % 2가 될거임.근데 sum_of_digit(a[i]*x) 값이 궁금한게 아니고 이게 홀수인지 궁금한거니까sum(sum_of_digit(a[i]*x)%2) % 2 로도 표현 할 수 있음.근데 각 자리수의 후보가 될 수 있는 수들은 [0..9] 인데, 0은 어차피 뭘 곱해도 0이니까 빼고 생각하면 [1..9]에 같은 x를 곱했을 때 나올 수 있는 sum_of_digit(a[i]*x) % 2의 집합의 경우의 수는 최대 2^9 = 512가지 일거임.

[ㅅㅅ(59.152)]

그런데 코드를 통해 확인해보면 x < 12000인 x에 대해 위에서 말한 모든 조합이 다 등장함. 따라서 수에 12000이하의 수를 곱해가면서 모든 경우를 확인해보면 됨. (만약 그래도 안 나오면 불가능한 경우) 여담으로 불가능한 경우를 생각해보면 원래 숫자의 모든 자리수가 같은 자리값을 가지는 것들이 다 짝수개인 경우에 대해서만 불가능하다는 것을 알 수 있음. (그것들은 어차피 계속 곱해봐야 짝수니까)

[ㅅㅅ(59.152)]

근데 될 지는 나도 아직 안 해봐서 모름

[ㅅㅅ(59.152)]

아 근데 숫자 합쳐질 때 예외가 있네 흠...

[메리체리(mrscherry)]

공식풀이는 1줄컷임ㅋ