[442] 백준 1979번 - 극적인 곱셈

1.  문제

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

2. 문제 이해

n, k 가 주어졌을 때, 위 그림과 같이 k로 끝나는 어떤 수에 n을 곱한 결과가 그 어떤 수를 오른쪽으로 한 칸씩만 옮겨진 수와 같은 결과가 되도록 하는 어떤 수를 구하는 문제입니다.

3. 해결 방법

찾고자 하는 수의 일의 자리 숫자는 무조건 k입니다.

따라서 n을 곱한 값의 일의 자리 숫자는 (k*n)%10이고, 구하고자 하는 어떤 수의 십의 자리도 (k*n)%10이 됩니다.

이제 구한 수를 a라고 하면 n을 곱한 값의 십의 자리 숫자는 (a*n)%10 에 (k*n)//10을 더한 값이 됩니다.

그리고 그 수는 구하고자 하는 수의 백의 자리 값이 됩니다.

이제는 이 과정을, 곱한 값에 다시 k가 나올 때까지 반복합니다.

4. 문제점

곱한 결과 값에 다시 k가 나왔다고 바로 답을 구할 수 있는 것은 아닙니다.

왜냐하면 받아올림 해야할 수가 남아있으면 곱한 결과 값의 맨 앞자리 수가 k가 아니기 때문입니다.

5. 발상의 전환

문제에서 n과 k의 범위가 1부터 9까지입니다.

그렇다면 우리가 구해야할 답의 경우의 수는 9 * 9 = 81가지입니다.

경우의 수가 많지 않기 때문에 그냥 81가지의 답을 모두 구해서 제출해도 될 것 같습니다.

 

위에서 알아본 방법으로 일일이 찾아서 답을 구해볼 수 있습니다.

아래는 일일이 찾아본 결과입니다.

res = [
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [0, 105263157894736842, 157894736842105263, 210526315789473684, 263157894736842105, 315789473684210526, 368421052631578947, 421052631578947368, 473684210526315789],
    [0, 0, 1034482758620689655172413793, 1379310344827586206896551724, 1724137931034482758620689655, 2068965517241379310344827586, 2413793103448275862068965517, 2758620689655172413793103448, 3103448275862068965517241379],
    [0, 0, 0, 102564, 128205, 153846, 179487, 205128, 230769],
    [0, 0, 0, 0, 102040816326530612244897959183673469387755, 122448979591836734693877551020408163265306, 142857, 163265306122448979591836734693877551020408, 183673469387755102040816326530612244897959],
    [0, 0, 0, 0, 0, 1016949152542372881355932203389830508474576271186440677966, 1186440677966101694915254237288135593220338983050847457627, 1355932203389830508474576271186440677966101694915254237288, 1525423728813559322033898305084745762711864406779661016949],
    [0, 0, 0, 0, 0, 0, 1014492753623188405797, 1159420289855072463768, 1304347826086956521739],
    [0, 0, 0, 0, 0, 0, 0, 1012658227848, 1139240506329],
    [0, 0, 0, 0, 0, 0, 0, 0, 10112359550561797752808988764044943820224719]
]

 

입력 범위가 크지 않은 경우, 차라리 모든 경우의 답을 직접 구해서 제출하는 방법도 있다는 걸 알았습니다.