STUDY/알고리즘
[백준] 셀프 넘버 (Python)
seonyounggg
2021. 3. 1. 18:30
✏️ 문제
4673번: 셀프 넘버
셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때,
www.acmicpc.net
✏️ 풀이
- 1차시도
1부터 10001 까지에 대해 해당 자연수가 1부터 10000까지의 자연수 중 하나를 생성자로 가지는 지 판별하였다.
결과 : 시간 초과(O(n^2))
for num in range(1,10001):
for i in range(1,10000):
if i > num:
continue
if num == i + sum(list(map(int, list(str(i))))):
break
else:
print(num)- 성공
1부터 10000까지의 자연수를 생성자로 가지는 셀프넘버를 미리 모두 구하여 배열에 저장한다.
그 후, 1부터 10001까지에 대해 셀프넘버 배열에 속하지 않는 것들을 출력한다.
시간복잡도가 O(n)으로 줄어든다.
✏️ 코드
d = []
for i in range(1,10000):
d.append(i + sum(list(map(int, list(str(i))))))
for i in range(1,10001):
if i not in d:
print(i)