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

 

 

난이도: 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.

 

문제 예제

---

Example 1:

Input: n = 10
Output: 182
Explanation: There are exactly 3 integers i in the range [1, 10] that satisfy the conditions in the statement:
- 1 since 1 * 1 = 1
- 9 since 9 * 9 = 81 and 81 can be partitioned into 8 and 1 with a sum equal to 8 + 1 == 9.
- 10 since 10 * 10 = 100 and 100 can be partitioned into 10 and 0 with a sum equal to 10 + 0 == 10.
Hence, the punishment number of 10 is 1 + 81 + 100 = 182

Example 2:

Input: n = 37
Output: 1478
Explanation: There are exactly 4 integers i in the range [1, 37] that satisfy the conditions in the statement:
- 1 since 1 * 1 = 1. 
- 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1. 
- 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0. 
- 36 since 36 * 36 = 1296 and 1296 can be partitioned into 1 + 29 + 6.
Hence, the punishment number of 37 is 1 + 81 + 100 + 1296 = 1478

 

제한 사항

---

• 1 <= n <= 1000

 

✏️ Solution(솔루션)

---

class Solution:
    def punishmentNumber(self, n: int) -> int:
        answer = 0
        
        def partition(i, now, target, string):
            if i == len(string) and now == target:
                return True

            for j in range(i, len(string)):
                if partition(j + 1, now + int(string[i:j+1]), target, string):
                    return True
            return False

        for i in range(1, n + 1):
            if partition(0, 0, i, str(i * i)):
                answer += i * i 
        
        return answer

 

 

1 부터 n+1까지의 숫자(i)에 대해  i*i를 진행하여 파티셔닝했을 때 i값이 나오는지 검사를 진행했다.

 

검사는 재귀함수를 구현하여 진행했다. 만약 파티셔닝을 하고 그 값들을 더했을 때 i가 나온다고 한다면 True를 반환했다.

 

따라서, 1 ~ n+1까지 i*i값을 파티셔닝 하고 그 값을 더했을 때 i가 나오는 경우가 있으면 answer에 i*i 값을 더해주었다.

 

마지막에는 answer를 return하고 정답을 맞출 수 있었다

 

---

문제: 2698. Find the Punishment Number of an Integer

 

깃허브: github

algorithmPractice/LeetCode/2802-find-the-punishment-number-of-an-integer at main · laewonJeong/algorithmPractice