[AtCoder] E - Digit Sum Divisible

https://atcoder.jp/contests/abc336/tasks/abc336_e

E - Digit Sum Divisible

---

문제 요약

$N$보다 작거나 같은 수 중 Digit Sum으로 나누어 떨어지는 수의 개수를 구하라.

---

풀이

가능한 모든 Digit Sum에 대한 Digit DP 값들을 모두 더해주자.

 

Digit DP를 할 것이기 때문에, 주어진 수를 문자열로 바꾸어주자.

ex) 2024 → 00000000002024

 

dp[i][j][k][s][f]를 다음과 같이 정의하자.

i번째 숫자가 j

k는 (지금까지 정해진 수 % Digit Sum)

s는 지금까지 정해진 숫자들의 합

f는 지금까지 정해진 숫자들 중 주어진 수의 숫자보다 작은 숫자로 정한 적이 있는가?

 

f의 값에 따라 사용할 수 있는 j가 바뀌기 때문에, 이에 유의해서 DP식을 전이해 주면 답을 구할 수 있다.

 

코드

---

느낀 점

Digit DP임을 대회 중에 의심하고 실제로 DP식을 짜보려 했는데 실패했다.

아마 Digit DP에 대해 익숙해지지 않아서 그런 것 같다.

앞으로 Digit DP를 만나면 아래 항목들을 떠올려보자.

 

• 최대 자릿수를 정하자.
• 수를 문자열로 바꾼뒤, 숫자 하나씩 볼 때에는 큰 자릿수부터 보자.

이 문제에서는 최대 자릿수는 14이고, 큰 자릿수부터 보는 이유는 DP식의 전이가 편해지기 때문이다.

 

2023 ICPC 서울 리저널 끝나고 Digit DP 찍먹했었는데, 문제들이 하나하나 힘들어서 3, 4개만 풀고 던졌던 기억이 있다.

이때 좀 더 풀었더라면 아마 대회 중에 풀었을 지도..