[백준 / Python] 7117번 Sevens, twos and zeros

https://www.acmicpc.net/problem/7117

7117번: Sevens, twos and zeros

문제 분석

난이도

플래티넘5

분류

중간에서 만나기(MITM), 그래프 탐색, 너비우선탐색

들어가기 전에

중간에서 만나기 알고리즘을 알고 있어야 쉽게 풀 수 있는 문제

문제

최대 길이가 20이고 2, 7, 0으로 이루어진 0으로 시작하지 않는 수가 있다. 이 수들 중 n으로 나누어 떨어지는 가장 작은 수를 출력해라.

입력

n이 주어진다. n의 범위는 1<n<500000이다.

출력

조건을 만족하는 가장 작은 수를 출력하고, 만약 만족하는 수가 없다면 NAV를 출력해라.

문제 풀이

 

풀이

단순히 모든 경우의 수를 탐색하는 경우 2,7,0 3가지 숫자가 20개 놓일 수 있으므로 대략 3^20이고, 그 크기는 거의 35억이나 된다. 따라서 이렇게 단순하게는 풀 수 없고, 앞 뒤로 10칸씩 나누어서 풀어주면 된다!

3^10은 약 6만 정도로 충분히 적은 시간이다. 일단 조건에 길이가 10인 조건에 맞는 수들을 BFS로 구해준다. 이때 만들어진 수가 n으로 나누어떨어진다면 그 값 또한 정답이 될 수 있다. 그런데 그렇지 못해서 길이가 10칸을 넘는 수들의 경우 또한 찾아주어야 한다.

그리고 이 수들에 10^10을 곱해준다. 그러면 27의 경우 27 하고 0,000,000,000이 뒤에 붙게 된다. 이렇게 뒤에 0을 10개 붙여서 길이가 20인 수의 앞 / 뒤 부분을 나누어 줄 수 있다.

그리고 이렇게 만든 앞의 수의 나머지와 뒤의 수의 나머지의 합이 n이라면 그 앞과 뒤의 수를 합친 값이 정답이 될 가능성이 있는 것이다.

예를 들어 n이 482818라고 가정해보자, 길이가 10 이하인 수들 중에서는 조건을 만족하는 수가 존재하지 않는다.

7700027002%482818과 22270000000000%482818의 합은 482818이므로 22277700027002는 답이 될 수 있다.

이렇게 답을 여러개 구하고 최소값을 구해도 되지만 앞부분이 가장 작은 순서부터 탐색한다면 바로 정답을 구할 수 있다.

소스코드

from sys import stdin
from collections import defaultdict
input=stdin.readline

n=int(input())

dd=defaultdict(int)
case=[]

def bfs(now,le):
    if now!=0 and now%n==0:
        print(now)
        exit()
    if le==10:
        case.append(now)
        return
    bfs(now*10,le+1)
    bfs(now*10+2,le+1)
    bfs(now*10+7,le+1)

def mkfront():
    for i in range(1,len(case)):
        i=case[i]
        left=(i*10**10)%n
        if not dd[left]:
            dd[left]=i*10**10
        
            

bfs(0,0)
mkfront()
anslist=[]
for i in case:
    if n-i%n in dd:
        anslist.append(dd[n-i%n]+i)

print(min(anslist) if anslist else "NAV")

후기

BFS 태그가 달려있긴 하지만 BFS문제라고 보기는 힘들 것 같다.