[SCPC - 2018년 1차 예선] 회문인 수의 합 (JAVA)

문제

회문(回文)인 숫자는 왼쪽에서 읽으나, 오른쪽에서 읽으나 같은 숫자를 말한다.
예를 들어, 3, 121, 13231, 263362는 회문인 숫자이다. 

어떤 수 n이 주어졌을 때, 이 n을 회문인 숫자 최대 3개의 합으로 표현할 수 있는지 없는지 알려주고,
있다면 회문인 숫자들의 최소 개수의 합으로 표현하는 프로그램을 작성하시오.

예를 들어, 121은 그 자체가 회문인 숫자이므로 1개의 회문인 숫자 121로 표현이 가능하며,
15233은 15233 = 13231+2002과 같이 회문인 숫자 두 개의 합으로 나타낼 수 있다.
15237은 15237 = 13231 + 2002 + 4와 같이 회문인 숫자 세 개의 합으로 표현이 가능하다.
회문인 숫자들 중 같은 값이 있는 것도 허용된다.

 

 

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어지고,
이후 차례로  T개의 테스트 케이스가 주어진다. (1≤T≤30)(1≤T≤30)

각 테스트 케이스는 정확하게 하나의 정수 n(1≤n≤10,000)n(1≤n≤10,000)이 주어지며, 이 숫자가 최대 3개의 회문인 숫자들의 합으로 표현할 수 있는지 알아보려는 숫자이다. 

 

 

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.

그 다음 줄에 최대 4개의 정수를 출력한다. 처음 숫자 KK는, 입력받은 nn이 몇 개의 회문인 숫자의 합인지를 나타낸다.
만약 불가능하다면 0을 출력한다. 그 다음 K개의 숫자는, 합이 nn이 되는 K개의 회문인 숫자를 크기의 내림차순으로 출력한다.

K개의 숫자로 표현 가능한 둘 이상의 경우가 있다면, 이 중 하나를 출력한다. 

 

 

풀이

중복조합을 이용한 완전탐색으로 풀 수 있는 문제였습니다.

 

문제에서 요구하는 풀이 방법은 다이나믹 프로그래밍으로 예상되나... 능지가 딸려서 깔끔한 해결 방법이 영 떠오르지 않았습니다.

 

그래서 N의 최댓값을 보니, 10000이었고 10000만 이하의 팰린드롬 수는 고작 198개였습니다!

또한, N을 구성하는 팰린드롬의 수는 최대 3개이기때문에 단순히 198개의 수 중에서 2개 또는 3개를 뽑아서 그 요소들의 합이 N과 같은지 확인해도 시간초과가 발생하지 않았습니다.

 

따라서 위에서 언급한대로, 우리는 팰린드롬의 수 198개를 List에 저장해 놓고, N이 List에 존재하면 바로 출력합니다.

만약, N이 List에 존재하지 않다면, r이 2 혹은 3인 중복조합을 수행하여 해당하는 사이즈와 요소를 출력하면 됩니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.