[엘리스] 숫자놀이

숫자놀이

모두가 나른해지는 오후 4시. 공작부인의 티타임에 초대된 엘리스는 티타임 장소에 도착했어요.

 

“깔깔깔 체셔, 역시 이 게임은 너무 재밌어.” “저도 그렇게 생각합니다. 주인님 마침 엘리스가 도착했군요.” "엘리스 너도 이 게임을 해보지 않을래?"라고 체셔가 물어보자 엘리스가 답했어요.

 

“응, 나도 해보고 싶어. 그런데 무슨 게임이야??”

 

“이 게임에 규칙은 간단해. 내가 두 가지 숫자를 말하면 넌 주어진 조건에 해당하는 모든 숫자를 답하면 되는 거야” 체셔는 엘리스를 바라보며 환하게 웃으며 답했어요.

 

“규칙은 이거야, 내가 첫 번째로 말하는 숫자는 답해야 하는 숫자의 자릿수가 되고 두 번째 숫자는 자릿수 간에 차이가 되지. 예를 들어 내가 첫 번째 숫자로 2, 두 번째 숫자로 5를 말하면 네가 답해야 하는 숫자는 16, 27, 38, 49, 50, 61, 72, 83, 94가 되는 거야”

 

“그리고 대답해야 할 모든 숫자는 0으로 시작할 수 없어. 즉, 07처럼 대답하는 건 안돼.”

 

“어때? 정말 쉽지???”

 

하지만 문과인 엘리스는 이게 무슨 소린지 전혀 이해하지 못하고 있었어요. 여러분이 엘리스를 도와 즐거운 티타임에 어울릴 수 있도록 정답을 알려주세요!

입력 예시 1

2
5

출력 예시 1

16 27 38 49 50 61 72 83 94

입력 예시 2

4
6

출력 예시 2

1717 2828 3939 6060 7171 8282 9393

입력

• 첫 번째 줄에 자릿수(DigitDigit)가 주어집니다. (2 ≤ DigitDigit ≤ 9)
• 두 번째 줄에 자릿수 간에 차이(DifferenceDifference)가 주어집니다. (0 ≤ DifferenceDifference ≤ 9)출력
• 주어진 입력 값인 자릿수(DigitDigit)와 자릿수 간에 차이(DifferenceDifference)에 해당하는 숫자들을 공백을 기준으로 출력하세요.
• 출력하는 숫자의 순서는 오름차순으로 정렬되어 있어야 합니다.

풀이

• DFS를 이용해서 모든 경우에 대해 조사
• Product을 이용한 방식은 메모리에러 발생

def dfs(A): 
    '''
    1. 길이가 N보다 이하면 확인, N보다 이상이면 return A
    2. 재귀를 이용해서 확인 
        - 조건에 맞는 경우 dfs진행 
    '''
    result = []
    if len(str(int(A))) == N:
        result += [A]
    else:
        if len(A) <= N: 
            for i in range(0, 10):
                sol = A
                if abs(int(A[-1]) - i) == M:
                    sol = ''.join([sol, str(i)])
                    result += dfs(sol)
        else:
            return
    return result


N = int(input())
M = int(input())

result = []
for i in range(1, 10):
    result += dfs(str(i))

print(*result)

• Product를 이용한 완전탐색 (메모리에러) 

# 완전 탐색(product을 이용)
from itertools import permutations
from itertools import product

N = int(input())
M = int(input())


R = [str(c) for c in range(10)]
perR = list(map(''.join, product(R, repeat = N)))
# perR = list(map(''.join, permutations(R, N)))
# print(perR)

start_pt = 0
while start_pt != len(perR):
    if len(str(int(perR[start_pt]))) != N:
        perR.remove(perR[start_pt])
        start_pt -= 1
    else:
        for j in range(len(perR[start_pt])-1): 
            if abs(int(perR[start_pt][j]) - int(perR[start_pt][j+1])) != M:
                perR.remove(perR[start_pt])
                start_pt -= 1
                break
    start_pt += 1

print(*list(map(int, sorted(perR))))

 

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn