[BOJ 25180] 백준 25180번 - 썸 팰린드롬

May 16, 2022

1. 문제

백준 25180번 - 썸 팰린드롬 (https://www.acmicpc.net/problem/25180)

정해진 합을 최소 개수의 숫자를 사용해서 만들어야 하므로, 숫자가 최대한 커야 한다. 따라서 $9$를 최대한 많이 사용한다.

$N=26$ $\rightarrow$ $989$

$N=27$ $\rightarrow$ $999$

$N=28$ $\rightarrow$ $5995$

$N=30$ $\rightarrow$ $6996$

이를 통해, $N$을 $9$로 나누었을 때 몫을 사용해서 길이를 구할 수 있음을 알 수 있다.

int len = (N - 1) / 9 + 1;

단, 예외 케이스가 있다.

$N=29$ $\rightarrow$ $?99?$

$N$이 $29$인 경우, $9$ 두 개를 사용하게 되면, 나머지 합인 $11$로 두 개의 동일한 수를 만들어낼 수 없다. 따라서, 위의 경우에는 $9$를 세 개 사용해야 한다. 그럼 길이가 $1$ 더 증가하게 된다.

$N=29$ $\rightarrow$ $19991$

이를 통해, $N$이 홀수인데 len이 짝수가 나오는 경우, 위와 같은 예외상황이 발생하여 결과값에 $1$을 더해야 함을 알 수 있다. ($N$이 홀수더라도 len이 홀수이면, 가운데 수를 조정하면 되므로 상관이 없다.)