[BOJ] 백준 20500번 : Ezreal 여눈부터 가네 ㅈㅈ (JAVA)

문제

 

 

욱제는 15라는 수를 굉장히 싫어한다. 그래서 0으로 시작하지 않고 1과 5로만 구성된 N자리 양의 정수 중에서, 15의 배수가 몇 개인지 궁금해졌다.

 

참가자 여러분도 궁금하지요?

 

안 궁금함? 15ㄱ

 

 

입력

N이 주어진다.

 

 

출력

문제의 답을 1000000007로 나눈 나머지를 출력한다.

 

 

제한

1 <= N <= 1515

 

 

풀이

정수론 지식과 다이나믹 프로그래밍을 이용하여 풀 수 있는 문제였습니다.

 

먼저, 15의 배수의 조건을 파악해야 합니다. 15는 3과 5의 공배수이므로 3의 배수의 성질과 5의 배수의 성질을 모두 갖고 있습니다. 3의 배수는 각 자리 수의 합이 3으로 나누어 떨어지는 특징이 있고, 5의 배수는 일의 자리가 0 또는 5라는 특징이 있습니다. 따라서 15의 배수는 각 자리 수의 합이 3으로 나누어 떨어지는 동시에 일의 자리가 0또는 5이어야 합니다.

 

이때, 문제에서 N은 1또는 5로만 이루어진 수라고 하였으므로 일의 자리는 무조건 5로 고정이 됩니다. 즉, 우리는 일의 자리는 5로 고정한 후 나머지 수를 적절히 조합하여 각 자리 수의 합이 3으로 나누어 떨어지게 해야 합니다.

 

 

이번에는 시야를 조금 넓혀 봅시다. 우리의 목적은 각 자리 수의 합이 3으로 나누어 떨어지도록 만드는 것입니다. 하지만, (N - 1)자리 수의 각 자리 수의 합이 3으로 나누었을 때 나머지가 1이라면, 그 수에 5를 추가한 N자리 수의 각 자리 수의 합은 3으로 나누어 떨어지게 됩니다. 즉, 우리는 이 문제를 다이나믹 프로그래밍으로 풀 수 있게 됩니다. 그리고 점화식은 아래와 같이 표현할 수 있습니다.

 

 

dp[i][j]를 길이가 j인 수의 각 자리 수의 합을 3으로 나눈 나머지는 i라고 정의하면,

dp[0][j] = dp[1][j - 1] + dp[2][j - 1]

dp[1][j] = dp[0][j - 1] + dp[2][j - 1]

dp[2][j] = dp[0][j - 1] + dp[1][j - 1].

 

 

점화식을 정의하였으니 오버플로우에 주의하여 MOD 연산을 해 주시면 됩니다.

 

 

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

 

 

소스코드

 

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