오늘의 문제 - boj-20500

문제

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

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

안 궁금함? 15ㄱ

풀이

1. 테이블 정의
   dp[i] = i번째 자리의 1 or 5로 구성된 15의 배수의 갯수
2. 점화식
   그냥 봐서는 규칙을 잘 모르겠어서 꽤 머리를 싸맸다. 우선 10억개의 이터레이션을 돌려서 각 자리의 수들이 어떤 규칙으로 만들어지는가를 살펴보았다.

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

3. 초기값
   dp[1] = 0

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문제를 하루에 하나씩은 꼭 풀어야겠다.