욱제는 15라는 수를 굉장히 싫어한다. 그래서 0으로 시작하지 않고 1과 5로만 구성된 N자리 양의 정수 중에서, 15의 배수가 몇 개인지 궁금해졌다.
참가자 여러분도 궁금하지요?
안 궁금함? 15ㄱ
import re
length = int(1e9)
for i in range(length):
if re.findall('[^15]', str(15*i)):
continue
print(15 * i)
처음에 1과 5로만 구성됐다는 부분이 or 인지 and인지 좀 헷갈려서 555를 포함시켜야 하나 고민이 있었다. 우선 예제에는 세자리의 갯수가 1개로 나와있고 세자리 중에 15의 배수이면서 1과 5 모두 포함하는 수는 없으니까 or라고 받아들이고 규칙을 찾아보았다.
혹시 15의 배수별로 특징을 가지지 않을까 싶어서 첫 몇개의 수들을 살펴봤으나 딱히 규칙성을 발견하기는 어려웠다.
dp문제니까 혹시 자릿수별로 갯수의 규칙이 있지 않을까 해서 봤더니 규칙이 있었다.
0, 1, 1, 3, 5, 11, 21 순으로 증가하는 자릿수의 갯수를 보면 i번째 숫자가 홀수면 (i-1) 2 - 1 의 값을 가지는 것을 알 수 있고 짝수면 (i-1) 2 + 1의 값을 가지는 것을 알 수 있다.
따라서 점화식은 다음과 같다.
if i is 홀수
dp[i] = dp[i-1] 2 -1
if i is 짝수
dp[i] = dp[i-1] 2 +1
N = int(input())
dp = [0] * (1516)
for i in range(2, N+1):
if i % 2 == 0:
dp[i] = (dp[i-1] *2 +1) % 1000000007
else: dp[i] = (dp[i-1] *2 -1) % 1000000007
print(dp[N])
다른 사람들의 풀이를 보니까 내가 진짜 수학적 사고가 많이 부족하다는 것을 느낀다. 내가 어려움을 느끼는 구간은 대체로 수학적 사고의 부족이었으니까 이런 류의 문제를 통해서 사고의 확장이 필요함을 느낀다.
내일부터 다른 알고리즘을 공부할 예정이지만 dp문제를 하루에 하나씩은 꼭 풀어야겠다.