https://www.acmicpc.net/problem/2023
문제 해석
왼쪽 부터 1자리, 2자리, 3자리, 4자리 순으로 n이 주어지면 n자리 까지의 모든 수가 소수인 수를 구하는 문제이다.
코드
def go(t):
# 소수 체크 #
flag = True
i = 2
while i * i <= t:
if t % i == 0:
flag = False
break
i += 1
if flag: # 소수가 참일 때 현재 소수 * 10 + i를 하여 다시 체크
for i in range(1,10):
go(t*10 + i)
else: return # 거짓일 때 return
# -------------------- #
# m자리가 될 때 출력
if len(str(t)) == m:
print(t)
return
m = int(input())
for i in range(2,10):
go(i)
문제 풀이
백트래킹을 사용하여 푸는 방법을 생각해보았다.
첫째 자리부터 2부터 9까지 재귀함수에 대입하여 소수 판별을 한 후 다음 자리수를 하나씩 대입하여 소수 판별을 하면 된다.
먼저 소수 판별하는 방법은 2 ~ n-1 까지의 수를 나누어 보았을때 나머지가 없어야 한다.
하지만 이 방법으로는 시간복잡도가 O(N) 이 되기때문에, 훨씬 시간이 적게 드는 방법을 사용했다.
2 ~ √(n-1) 까지만 나누어보아도 소수 판별이 가능하다.
재귀함수 go(t)를 해석하면
먼저 소수를 판별한다. 루트를 사용하면 표기상 불편하기 때문에 i*i 을 사용했다.
소수가 맞다면 flag = True값이 되고, 다음 for문을 통해 t * 10 + 1 ~ 9 까지 들어가게 된다.
#( 0을 넣으면 2로 나누어지기 때문에 1부터 넣었다. )
이후 문제에서 원하는 m자리 까지 도달하면 출력한다.
m자리를 받고 반복문을 통해 2 부터 9까지 수를 넣었다.
#( 0과 1은 재귀함수가 아니기 때문에 2부터 넣었다. )
원문
https://ddingmin00.tistory.com/22
'Koala - 5기 > 기초 알고리즘 스터디' 카테고리의 다른 글
[백준/python] 17608 막대기 (0) | 2022.02.28 |
---|---|
[백준/c++] 3029번 경고 (0) | 2022.02.28 |
[BOJ / PYTHON ] 15649 N과M (0) | 2022.02.26 |
[백준/python] 1032번 명령 프롬포트 (0) | 2022.02.21 |
<6주차> [BOJ / C++] 1932번 - 정수 삼각형 (0) | 2022.02.20 |