[풀이] 1131 (숫자) P5 풀이

주의 : 좋 고수 Ps 갤 이용자 분들은 봐주셔도 됩니다!

좋 초보 이용자 분들도 보시는 걸 추천 드려요!

개추 3개로 날먹 하는 풀이러 면 개추 ㅋㅋ

문제 설명

문제

자연 수 N이 주어졌을 때, N의 각 자리 수를 K제곱 한 후에 그 합을 구하는 함수를 SK(N)이라고 하자. 예를 들어, S2(65) = 62 + 52 = 61이다.

이제 다음과 같은 수열을 하나 만들어보자. N, SK(N), SK(SK(N)), … 이때, A와 B와 K가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 모든 N으로 각각 수열을 만들었을 때, 그 수열에서 가장 작은 수의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, K가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다.

풀이

enum { WHITE, GRAY = -1 }; 으로 열거형 상수를 만들어준다.

그 다음 DP 배열을 만들고

정수 a, b, k와 보조 배열을 하나 만들자.

자 그러면 Init 함수로 거듭 제곱을 계산해서 배열에 저장하고

f 함수로 주어진 숫자의 각 자릿수를 가져와서 해당 자릿수의 거듭 제곱의 합을 반환하고

DFS 함수로 DFS를 수행한다. DP 배열을 이용해 방문한 노드인지 확인해준다.

방문하지 않은 경우(WHITE)에는 GRAY로 표시하고, 해당 노드를 기준으로 다음 노드를 방문한다.

GRAY인 경우에는 해당 노드부터 사이클이 존재하는 부분까지 탐색하여 최소 값을 찾고, 그 값을 DP 배열에 저장한다.

이제 Init을 불러오고

숫자를 입력 받아 DFS를 실행하고 출력하면 된다.

"플레 5다"

댓글 2