[백준] 30469 | 호반우가 학교에 지각한 이유 2 [파이썬/python]

문제

link: https://www.acmicpc.net/problem/30469

두 소수 A, B를 입력받아 A로 시작하고 B로 끝나는 길이 N의 소수소수를 만드는 문제이다.

소수소수는 해당 수 자체가 소수일 필요는 없지만 모든 연속된 두 자릿수가 소수인 수를 말한다.

 

접근

처음에는 dfs를 활용해 코드를 작성했는데 시간 초과가 발생해 다른 방법으로 접근하기로 했다.

아래 사진은 dfs로 코드를 짰을 때 만들었던 2차원 리스트의 내용물이다. 10 이상 99 이하의 소수를 저장한 목록인데, 십의 자리 숫자 인덱스로 접근할 수 있는 리스트에 일의 자리 숫자를 저장하도록 했다. 살펴 보니 두 자릿수 소수의 일의 자리 숫자는 1, 3, 7, 9 중 하나였다. 짝수일 경우 2의 배수이고 5로 끝나는 경우에는 5의 배수이므로 소수가 될 수 없다.

따라서 다음 항목들에 유의해 코드를 작성했다.

1. B의 십의 자리 숫자가 1, 3, 7, 9가 아닐 경우 -1을 출력하고 프로그램을 종료한다.

2. 11, 13, 17, 19가 소수이므로 십의 자리 숫자가 1인 경우 1, 3, 7, 9로 시작하는 모든 두 자릿수 소수에 접근할 수 있다. 가능한 것 중 아무 소수나 출력하면 되므로 A와 B 사이를 11로 채우게끔 한다.

3. 11, 31, 71은 소수이지만 91은 소수가 아니다. 십의 자리 숫자가 9인 것 중 소수인 수는 97뿐이므로 A의 일의 자리 숫자가 9인 경우 97->71->11로 이어지도록 만든다.(N의 범위가 7<=N<=100이므로 문제가 되지 않는다.)

 

코드

A, B, N = map(int, input().split())
sosus = [1]*100
s = set([1, 3, 7, 9])
ans = ['1']*N
for i in range(2, 100):
    for j in range(i*i, 100, i):
        sosus[j] = 0
        
if not sosus[A] or not sosus[B]:
    print(-1)
elif B//10 not in s:
    print(-1)
else:
    ans[0] = str(A//10)
    ans[1] = str(A%10)
    if ans[1] == '9':
        ans[2] = '7'
    ans[-2] = str(B//10)
    ans[-1] = str(B%10)
    print(*ans, sep='')

위 코드에는 A와 B가 소수인지 검증하는 if문이 들어가 있는데, 문제에서 제공하는 A와 B 값이 소수로 한정되어 있으므로 사실 이 부분은 필요하지 않다.