백준 3130번 붙인드롬

문제 설명

이번 문제는 길이가 같은 펠린드룸 두개를 나란히 붙여서 길이가 N인 수를 만들 때, M으로 나누어 떨어지는 개수를 구하는 문제입니다.

 

문제 풀이

아이디어

팰린드롬 구하기

구하고 싶은 팰린드롬의 길이 n이 짝수일 경우 

0~9 숫자 n//2개의 중복순열의 개수가 답이 됩니다.

예) 4자리의 팰린드룸을 구하면,

0000, 0110, 0220, 0330, ....

위와 같이 2자리 수와 2자리 수를 뒤집은 수를 합치면 팰린드롬이 됩니다.(00, 01, 02, 03, ....)

그러므로 4자리의 팰린드룸 개수는 10^2가 됩니다.

 

구하고 싶은 팰린드룸의 길이 n이 홀수일 경우

(0~9 숫자 n//2개의 중복순열의 개수) * (중간에 올 수 있는 수 10개)

예) 5자리의 팰린드룸을 구하면,

00000, 01010, 02020, 03030, ... , 00100, 01110, 02120 ...

길이가 짝수인 팰린드롬을 구할 때와 마찮가지로 n//2 자리수와 n//2 자리수를 뒤집어 놓은 수가 양쪽에 위치하게 되고,

중간에 0~9가 들어갈 수 있으므로 해당 경우의 수(10)를 곱해주면됩니다.

 

나머지 구하기

a+b를 m으로 나눈 나머지는 a를 m으로 나눈 나머지와 b를 m으로 나눈 나머지의 합을 m으로 나눈 나머지입니다.

 

앞 뒤로 팰린드룸을 붙일 경우(앞에 위치한 팰린드룸=a, 뒤에 위치한 팰린드룸=b, 팰린드룸의 길이=l)

두 팰린드룸을 붙인 숫자는 a*10^l + b 가 됩니다.

그러므로 이 숫자를 m으로 나눈 나머지는 ((a*10^l)%m + b%m)%m입니다.

 

나누어 떨어지는 수 찾기

위와 같이 두 개의 숫자(a,b)를 붙여 나머지를 찾을 경우 결국엔 a를 나눈 나머지, b를 나눈 나머지의 합을 m으로 나눈 나머지가 답이됩니다.

그러므로 m으로 나누어 떨어지는 수를 구하려면, 두 수를 m으로 나눈 나머지의 합이 m으로 나누어떨어지는 수를 구해야합니다.

즉, 두 수를 m으로 나눈 나머지의 합이 0이거나 m이면 됩니다. (x<m, y<m 인 두 수 x+y의 최대는 2*m보다 무조건 작기 때문)

 

풀이

길이가 N//2인 팰린드롬 구하기

구하고자 하는 붙인드롬의 길이//2의 짝수 홀수 여부에 따라 팰린드롬을 구해줍니다.

 

팰린드롬 나머지 저장 변수 선언

팰린드롬을 m으로 나눴을 경우 생길 나머지 별로 팰린드롬을 저장하기 위해 길이가 M인 배열 remain1, remain2를 선언해줍니다.

remain1은 앞에 붙을 팰린드롬, remain2는 뒤에 붙을 팰린드롬을 위한 것입니다.

팰린드룸의 나머지 저장하기

구한 팰린드룸이 앞에 올 경우 10^(팰린드룸의 길이)를 곱해줘야 됩니다.

(이 후부터 10제곱을 곱한 팰린드롬을 앞 팰린드롬, 기존의 팰린드롬을 뒤 팰린드롬이라고 부르겠습니다.)

 

앞 팰린드롬을 m으로 나눈 나머지를 r1, 뒤 팰린드룸을 m으로 나눈 나머지를 r2라고 하고,

앞 뒤 팰린드롬의 나머지를 저장할 수 있는 배열 각각의 배열 remain1, remain2에 넣어줍니다.

if {해당 팰린드룸 맨 앞의 숫자가 0이 아닐 경우}:
	remain1[r1].append({해당 팰린드롬})
remain2[r2].append({해당 팰린드롬})

 

나누어떨어지는 수 찾기

- 두 나머지의 합이 M이 되는 경우

반복문(1~M-1)을 돌면서 remain1[i]에 들어있는 팰린드롬과 remain2[-i]에 들어있는 팰린드롬을 두 개 나란히 붙일 수 있는 경우의 수

len(remain1) * len(remain2)를 결과값에 더해줍니다.

 

- 두 나머지의 합이 0이 되는 경우

나머지가 0인 두 팰린드롬을 나란히 붙일 경우의 수 len(remain1[0]) * len(remain2[0])를 결과값에 더해줍니다.

 

 

해결

이번 문제는 나머지의 합을 통해 나누어 떨어지는 수를 구해야겠다는 생각을 하기전까지 시간이 오래걸렸던 문제입니다.

 

문제 링크 : https://www.acmicpc.net/problem/3130

3130번: 붙인드롬

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/3130.py