파이썬으로 n을 3과 7의 배수의 합으로 표현할 수 있는지 확인하는 방법

문제 개요

양수 n이 주어졌을 때, 이 숫자를 3의 음수가 아닌 배수와 7의 음수가 아닌 배수의 합으로 표현할 수 있는지 확인하는 문제입니다.

예를 들어, 입력값이 13이라면 결과는 True입니다. 왜냐하면 13은 다음과 같이 표현할 수 있기 때문입니다.

1 × 7 + 2 × 3 = 13

해결 접근 방법

이 문제는 간단한 반복문을 통해 해결할 수 있습니다.

• 0부터 n까지 7씩 증가시키면서 반복합니다.
• 각 단계에서 (n - i)가 3으로 나누어 떨어지는지 확인합니다.
• 나누어 떨어진다면 해당 조합이 존재한다는 의미이므로 True를 반환합니다.
• 모든 경우를 확인한 후에도 찾지 못했다면 False를 반환합니다.

여기서 i는 7의 배수를 나타내며, n-i가 3의 배수라면 n은 7의 배수와 3의 배수의 합으로 표현 가능합니다.

구현 예제

class Solution:
    def solve(self, n):
        for i in range(0, n+1, 7):
            if (n-i) % 3 == 0:
                return True
        return False

ob = Solution()
print(ob.solve(13))

입력

13

출력

True

복잡도 분석

시간 복잡도는 O(n/7), 즉 사실상 O(n)입니다. 공간 복잡도는 추가 메모리를 사용하지 않으므로 O(1)입니다.

참고: 수학적 최적화

흥미로운 점은 체커바운드 정리(Checkerboard theorem)에 따르면, 6보다 큰 모든 정수는 3과 7의 배수의 합으로 표현할 수 있다는 것이 알려져 있습니다. 따라서 실제로는 작은 값에 대해서만 검증하면 되지만, 위의 일반적인 반복문 방식이 가장 직관적이고 안전한 구현 방법입니다.