숫자 - 1131
[Platinum V] 숫자 - 1131
1️⃣ 분류
다이나믹 프로그래밍(dp), 그래프 이론(graphs), 그래프 탐색(graph_traversal)
2️⃣ 문제 설명
자연수 N이 주어졌을 때, N의 각 자리수를 K제곱 한 후에 그 합을 구하는 함수를 SK(N)이라고 하자. 예를 들어, S2(65) = 62 + 52 = 61이다.
이제 다음과 같은 수열을 하나 만들어보자. N, SK(N), SK(SK(N)), … 이때, A와 B와 K가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 모든 N으로 각각 수열을 만들었을 때, 그 수열에서 가장 작은 수의 합을 구하는 프로그램을 작성하시오.
3️⃣ 입력
첫째 줄에 세 정수 A, B, K가 주어진다.
4️⃣ 출력
첫째 줄에 문제의 정답을 출력한다.
🔓 풀이
-
문제만 보면 수열에서 어떤 규칙성이 바로 보이지 않아서 작은 N에 대해 수열들을 한 번 나열하는게 좋다
Ex 1 : K = 2, N = 2 ~ 4
-
N = 2 2, 4, 16, 37, 58, 89, 145, 42, 20, 4, 16, 37, 58, 89 … -
N = 3 3, 9, 81, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, 58 … -
N = 4 4, 16, 37, 58, 89, 145, 42, 20, 4, 16, 37, 58, 89 …
Ex 2 : K = 4, N = 1 ~ 4
-
N = 1 1, 1, 1, 1, … -
N = 2 2, 16, 1297, 8979, 19619, 14420, 529, 7202, 2433, 434, 593, >7267, 6114, 1554, 1507, 3027, 2498, … -
N = 3 3, 81, 4097, 9218, 10674, 3954, 7523, 3123, 179, 8963, 12034, >354, 962, 7873, 8979, 19619, 14420, … -
N = 4 4, 256, 1937, 9044, 7073, 4883, 8529, 11298, 10675, 4323, …
-
- K = 2일 때, N = 2 일 때를 보면 2, 4, 16, … 가다가 4를 만나고 이후로 16, 37,… 반복 하는 걸 볼 수 있음
- 계속 성장하는 수열의 각 원소를 방문체크를 해서 방문체크에 있던 게 또 나오면 사이클이 시작된다는 소리라고 판단
- 이후 사이클에 들어 있는 원소들은 계속해서 그 사이클 내에서 놀 거 니깐
그 사이클내에 있는 최솟값이 그 원소들의 최솟값임을 이용 - 즉 계속 성장하는 수열을 DFS로 방문체크를 하고, 이미 최솟값이 정해진 N에 대해서는 DFS를 하지 않고 건너뛰면 되니깐 시간초과를 방지함
😝 구현
- EX) K = 4, N = 8
- 8 -> 4096 -> 8113 -> 4179 -> 9219 -> 13139 -> 6725 -> 4338 -> 4514 -> 1138 -> 4179 -> 9219 -> 13139 -> 6725 -> 4338 -> 4514 -> 1138 ->
- 4179 부터 사이클이 발생했으니 사이클 내 각각의 값들이 N일 때(수열의 시작값일 때) 수열의 최솟값은 1138 그러나 !! 처음 8은 아니다 8 이후에 나오는 어떤 값도 8보다 작은 값이 없어서 최솟값은 8이다!
-
노드들의 처음 값을 초기화 해서 계속해서 Min 값으로 갱신할려면 최댓값을 알아야한다 N은 최대 1,000,000 이므로 999,999 이고 K = 6이면 3,720,087로 이것 보다 크면 된다.
- cycle을 발견할 때 까지 N의 min(N, dfs(next))를 해서 수열을 성장해 간다
- cycle을 발견하면 cycle을 돌려서 최솟값을 찾는다
- 이후 노드들에 최솟값을 갱신함
INF = 9876543210
cache=[INF]*10000001 # 노드들을 처음 값으로 무한 값으로 초기화
A, B, K = map(int, input().split())
def dfs(n):
# 처음 방문 노드
if cache[n] == INF:
cache[n] = 0 #임시마크
n_next = sum(int(ch)**K for ch in str(n))
# n수열내에서 최솟값을 찾기 위함
cache[n] = min(n, dfs(n_next))
# INF 값이 아니라면 처음 방문 노드가 아니고
# 예를 들어 n = 2일 때, cache[n] = min(n, dfs(n_sum)) 에서
# n_sum = 2, 4, 16, 37, 58, 89, 142, 42, 20, 4
# n_sum은 4일 때 cache[n_sum] = 0이니깐 else로 들어 올 수 있음
# 즉 이제 한 사이클로 다 돌았고 이후에 4, 16, 37, 58, 89, 142, 42, 20 반복
else:
# (방문 했고,)
# 처리가 된 n값이라면
if cache[n] :
return cache[n]
minimum = n
nn = sum(int(ch)**K for ch in str(n))
# 또 사이클을 돌 거임
# 왜냐하면 사이클에서 가장 작은 최솟 값을 구하기 위해
# 사이클에서 가장 작은 최솟 값은 사이클에 속하는 n 값들의 최솟값도
# 같으니깐
while nn != n:
minimum = min(minimum, nn)
nn = sum(int(ch)**K for ch in str(nn))
# 사이클 내 최솟값 찾음
cache[n] = minimum
nn = sum(int(ch)**K for ch in str(n))
# 사이클 내 노드들에 최솟값 삽입
while nn != n:
cache[nn] = minimum
nn = sum(int(ch)**K for ch in str(nn))
return cache[n]
print(sum(dfs(i) for i in range(A, B+1)))
🤣 고찰
처음 뭔가 어려울 것 같다는 생각을 미리 했고 어떤 식으로 풀 지 감을 잡았다(오 DFS로 수열을 성장해나가고 cycle이 생기니깐 cycle이 생길 때까지의 최솟값을 구하면 되겠구나!). 그러나 코드를 구현하면서도 시간초과를 예상했고 vscode내에서 돌릴 때도 시간이 오래 걸렸다. 하루 정도 시간이 걸린거 같다 ㅠ 근데 풀이에 사용한 기술은 맞았지만 접근 방법이 잘 못 됐다…dp를 dp[2], dp[4], dp[16] 이런 식으로 채워나갔다 근데 이는 K=2일 때만 되는 거여서 결론은 초기 접근 방법부터 잘 못 됐었다… 그래서 벽을 느껴 구글링도 했는데 c++ 구현만 있었다… ㅠ 풀이를 얻어서 해당 문제가 들어있는 책을 참고해서 이해하고 다시 풀었다 … -> 벽을 느꼇지만 진득하게 하루종일 한 문제를 푼 경우가 오랜만이여서 너무 뿌듯하고 성장하는 기분이 너무 좋다!! 결과도 중요하지만 과정도 중요한게 아니겠나 ㅎㅎ….
댓글남기기