[LeetCode] 2698. Find the Punishment Number of an Integer

https://leetcode.com/problems/find-the-punishment-number-of-an-integer/

leetcode - FInd the Punishment Number of an Integer

문제 유형: 백트래킹

문제 난이도: Medium

 

문제

Given a positive integer n, return the punishment number of n.

The punishment number of n is defined as the sum of the squares of all integers i such that:

• 1 <= i <= n
• The decimal representation of i * i can be partitioned into contiguous substrings such that the sum of the integer values of these substrings equals i.

양의 정수 n이 주어집니다. n의 punishment number를 반환하시오.

n의 punishment number는 1 <= i <= n에서 i*i의 문자열로 하고 임의의 부분문자열로 나눠서 그의 정수 표현을 모두 더한 값이 i인 숫자를 말합니다.

 

풀이

dfs를 돌리는데, 문자열 s를 i^2의 문자열 표현으로 한다.

int index = 0, int sum = 0, string s, int target = i로 시작해서, 

index == s의길이면 sum == target을 반환한다.

그게 아니면, num = 0부터 시작해서, i를 index부터 시작해서, num에 i를 맨 뒤에 붙이는 식으로 숫자를 키워가면재 재귀호출을

dfs(index+1, sum+num, s, target)으로 호출한다.

한 번이라도 true가 나오면, true를 반환해주면 된다.

 

이 체킹이 true가 나오면, 유효하므로, i^2를 누적한다.

 

코드

C++

class Solution {
public:
    bool check(int x) {
        int v = x*x;
        string s = to_string(v);
        return dfs(s, 0, 0, x);
    }
    bool dfs(const string &s, int index, int sum, int x) {
        if(index == s.size()) return sum == x;

        int n = 0;
        for(int i = index; i < s.size(); ++i) {
            n = n*10 + (s[i] - '0');
            if(dfs(s, i +1, sum + n, x)) return true;
        }
        return false;
    }
    int punishmentNumber(int n) {
        int ans = 0;
        for(int i = 1; i <= n; ++i) {
            if(check(i)) {
                ans += i*i;
            }
        }
        return ans;
    }
};

 

Go

func check (x int) bool {
	v := x * x
	s := strconv.Itoa(v)
	return dfs(s, 0, 0, x)
}

func dfs(s string, index, sum, x int) bool {
	if index == len(s) {
		return sum == x
	}
	
	num := 0
	for i := index; i < len(s); i++ {
		num = num * 10 + int(s[i] - '0')
		if dfs(s, i+1, sum + num, x) {
			return true
		}
	}
	return false
}

func punishmentNumber(n int) int {
	ans := 0
	for i := 1; i <= n; i++ {
		if check(i) {
			ans += i*i
		}
	}
	
	return ans
}