문제 링크
https://www.acmicpc.net/problem/2331
문제 유형
DFS/BFS
🌈문제
다음과 같이 정의된 수열이 있다.
D[1] = A
D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합
예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.
이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 [57, 74, 65, 61]의 네 개의 수가 남게 된다.
입력
첫째 줄에 A(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5)가 주어진다.
57 2출력
첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.
4💡 아이디어
처음 문제 볼 때 굉장히 쉽다고 느껴졌다. 내가 생각했던 과정은 아래와 같다.
1. 처음 주어진 A의 값을 리스트에 집어넣는다.
2. 리스트 while문을 돌리면서 다음 인덱스로 등장할 값을 계산한다.
3. 만약 계산한 값이 리스트 내에 존재한다면 while문을 break하고 해당 인덱스를 찾아내 결과로 반환한다.
애초에 해당 문제는 DFS/BFS로 구분이 되어 있었는데 문제를 보았을 때, DFS로 풀어야 겠다는 생각이 하나도 들지 않았었기 때문에 문제를 어떤 관점에서 바라보아야 DFS/BFS로 풀어야겠다는 생각이 들까? 라는 점이 궁금해져서 이 포스팅을 작성하게 되었다.
👨💻 코드 작성
먼저 내가 처음 냈던 아이디어에 대한 코드이다.
A, P = map(int, input().split())
numlist = []
def calnum(num, P):
a = []
while (num != 0):
a.append(num % 10)
num = num // 10
number = 0
for i in range(len(a)):
number = number + a[i] ** P
return number
numlist.append(A)
i = 0
while True:
num = numlist[i] #인덱스 뽑아서
nextnum = calnum(num, P) #다음 인덱스값 계산
if nextnum not in numlist:
numlist.append(nextnum)
i += 1
else:
indx = numlist.index(nextnum)
print(indx)
break조금 복잡하게 작성한 감이 없지 않아 있다.. 찾아보니까 엄청 짧고 간결하게 작성한 코드도 있더라.
nums = [A]
for s in nums[-1]
tmp += s ** P이렇게 작성하면 calnum 함수 따로 안만들어도 된다. 다음부터 참고해서 코드짜보자. 자, 이건 이제 단순하게 생각해서 for문으로 돌려 짠 코드이고, 아래 질문을 참고해서 BFS로도 구현해보자.
답변하신 것 중에 인상깊었던 것은 아래 문장이다.
언젠가 이와 같은 반복수열이 된다.와 같이, 언제 끝날지 모르는 탐색문제는 BFS와 DFS로 풀이할 수 있습니다.
이 풀이는 visited를 탐색한다는 가정 하에 풀이할 수 있는 것이다. 앞으로 문제의 질문을 보고 의도를 꼼꼼히 파악하며 다르게 풀이할 수 없는지는 탐색하면서 풀어봐도 재미있을 것 같다.
A, P = map(int, input().split())
check = [0] * 250000 #최대 인덱스
count= 1
def cal(a, b):
result = 0
for i in str(a):
result += int(i) ** P
return result
def dfs(n, m, count, check):
if check[n] != 0: #만약 방문한 곳이라면 ?
return check[n] - 1 #결과 반환!
check[n] = count
count += 1
result = cal(n, m)
return dfs(result, m, count, check)
print(dfs(n, m, count, check))
