반응형
1131
-
1131번 : 숫자알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 14. 20:30
https://www.acmicpc.net/problem/1131 1131번: 숫자 자연수 N이 주어졌을 때, N의 각 자리수를 K제곱 한 후에 그 합을 구하는 함수를 SK(N)이라고 하자. 예를 들어, S2(65) = 62 + 52 = 61이다. 이제 다음과 같은 수열을 하나 만들어보자. N, SK(N), SK(SK(N)), … www.acmicpc.net i부터 시작해서 나열되는 수들 중 가장 작은 수의 합을 구하는 문제이다. 아이디어 : 그래프로 생각한다. 수 하나에서 시작하여 일정 수들을 거치면 항상 사이클이 생기는 것을 파악했다. 따라서 사이클에 속해있는 수들은 항상 똑같은 dp값을 가지고, 그게 아닌 수들만 따로 예외처리 해준다. 구현 : 먼저 p배열엔 0~9의 K제곱을 저장해준다. nxt엔 ..