해커랭크 Sam and substrings (C++)

안녕하세요~

오늘은 해커랭크 "Sam and substrings" 문제를 풀어봐요!

 

https://www.hackerrank.com/challenges/sam-and-substrings/problem?isFullScreen=true

Sam and substrings | HackerRank

 

주어진 문자열 속 숫자 조합의 총합을 구하는 문제에요!

하지만 단순 조합이 아니라 연속한 문자열이어야 한다는것!!

 

만약 "135"가 주어졌다면

1, 3, 5, 13, 35, 135를 더한 192가 정답이에요!

 

저는 처음에 일반 조합 재귀함수에

연속해야한다는 조건을 걸어서 풀다가

실패하고 다른분의 풀이를 참고했는데요!

 

DP로 풀어야 하더라구요 ^____^

완전 잘못짚었음...ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

아무튼 DP로 풀어야하기 때문에 점화식을 찾아야해요!

문자열의 각 요소별로

해당 요소가 포함된 숫자의 합을 구해볼게요!

 

"135"의 경우에서 생각하면

 

dp[0] = 1 // 0번째 요소인 1이 반드시 포함되는 숫자들의 합

dp[1] = 3 + 13 // 1번째 요소인 3이 반드시 포함되는 숫자들의 합

dp[2] = 5 + 35 + 135 // 2번째 요소인 5가 반드시 포함되는 숫자들의 합

 

이렇게 된답니다.

즉, 답은 dp[0] + dp[1] + dp[2] 에요.

 

자 그렇다면 우리는 n번째 dp[n]의 값에 대한 식만 구하면 되어요!

dp[2] = 5 + 35 + 135

이 식을 한번 볼게요.

 

dp[2] = 5 + (30 + 5) + (130 + 5)

2번째 요소인 5 기준으로 식을 바꿨어요.

5가 총 3회 나오죠?

 

dp[2] = 5 * 3 + 30 + 130

이렇게 고칠 수 있겠어요!

 

그리고 30과 130을 10으로 묶어줄게요.

dp[2] = 5 * 3 + 10 * (3 + 13)

자 여기서 빨간색 부분을 주목하세요.

5와 곱해진 3은 현재 index인 2에 1을 더한 값이에요.

그리고 (3 + 13)은 dp[1]의 값과 같죠?!!!!!

 

 

따라서 아래와 같이 고칠 수 있어요!

dp[2] = 5 * (2 + 1) + 10 * dp[1]

 

일반화 시키면

dp[n] = str[n] * (n + 1) + 10 * dp[n - 1]

 

짠! 이렇게 점화식이 나왔답니다.

 

이것을 코드로 옮기면 끝이에요!

 

전체코드 첨부할게요~

long long dp[200001];
int substrings(string n) {
    long long answer = 0;
    
    dp[0] = n[0] - '0';
    for(int i = 1; i < n.length(); i++)
    {
        dp[i] = (n[i] - '0')* (i + 1) + 10 * dp[i - 1];
        dp[i] %= 1000000007;
    }
    
    for(int i = 0; i < n.length(); i++)
    {
        answer += dp[i];
    }
    
    return answer% 1000000007;
}