주어진 숫자 n에 대해, 그 숫자를 구성하는 자릿수 중 하나라도 원래 숫자를 나누어 떨어지게 하는지 확인하는 것이 이번 과제입니다. 예를 들어 숫자 128625가 주어졌다면, 이 숫자는 5로 나누어 떨어지고 5는 실제로 이 숫자에 포함된 자릿수이므로 답은 '예'가 됩니다.
예제
입력: 53142 출력: Yes 설명: 이 숫자는 자릿수인 1, 2, 3으로 나누어 떨어집니다 입력: 223 출력: No 설명: 이 숫자는 2나 3 어느 쪽으로도 나누어 떨어지지 않습니다
접근 방식
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- 일의 자리부터 시작하여 가장 오른쪽 자릿수를 추출합니다.
- 해당 자릿수로 원래 숫자가 나누어 떨어지는지 확인합니다.
- 숫자를 10으로 나누어 다음 자릿수로 이동합니다.
- 숫자가 0이 될 때까지 위 과정을 반복합니다.
모든 자릿수를 검사했는데도 나누어 떨어지는 자릿수가 없다면 'No'를 반환합니다. 이 방법의 시간 복잡도는 자릿수의 개수에 비례하므로 O(d)(d는 자릿수 개수)로 매우 효율적입니다.
알고리즘
시작
함수 int divisible(long long int n)
1단계 -> temp = n 으로 선언 및 초기화
2단계 -> n이 참인 동안 반복 {
k를 n % 10 으로 설정 (일의 자리 추출)
만약 temp % k == 0 이라면,
1 반환 (나누어 떨어짐)
n = n / 10 으로 설정
반복 종료
0 반환 (나누어 떨어지는 자릿수 없음)
main 함수
1단계 -> n = 654123 으로 선언 및 초기화
2단계 -> divisible(n) 이 참이면,
"Yes" 출력
3단계 -> 아니면,
"No" 출력C 언어 구현 예제
#include <stdio.h>
int divisible(long long int n) {
long long int temp = n;
// 어떤 자릿수라도 n을 나누는지 확인
while (n) {
int k = n % 10;
if (temp % k == 0)
return 1;
n /= 10;
}
return 0;
}
int main() {
long long int n = 654123;
if (divisible(n)) {
printf("Yes\n");
}
else
printf("No\n");
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Yes
참고 사항
실제 응용 시에는 한 가지 주의할 점이 있습니다. 숫자에 0이 포함된 경우, 0으로 나눌 수 없기 때문에 나눗셈 연산 전에 자릿수가 0인지 먼저 검사하여 건너뛰는 처리를 추가하는 것이 안전합니다. 또한 long long int를 사용하면 매우 큰 정수도 오버플로우 없이 처리할 수 있습니다.