[백준] 2331번

문제출처: https://www.acmicpc.net/problem/2331

2331번: 반복수열

 

숫자 A,P가 주어지고, 처음은 A의 자릿수마다 P제곱 해준 값을 모두 더한 값으로 다음 수열값을 시작한다.

이후 그 뒤에 자릿수마다 P제곱의 합으로 다음 수열값을 만든다.

이걸 계속 하다보면 언젠간 같은 부분이 반복되는 지점이 생긴다. 그 반복되는 지점을 싹다 지우고,

남는 원소들의 개수를 구하는게 이 문제의 요지이다.

원소가 어떤게 남아있는지, 혹은 남은 원소의 모든 합을 구해도 좋을 것같은데

그렇게 하면 처리하는 시간이 더 오래걸려서 그냥 문제를 제한시간 2초에 개수를 구하라. 정도로 끝난것같다.

​

사실 dfs 공부를 하려고 dfs 관련 문제를 검색해서 풀었는데, 이 부분을 어떻게 dfs로 구현하는지는 의문이다.

(이 문제풀이의 다른 코드들을 찾아봐야겠다..!)

게다가 함수를 만들 필요도 없이 바로 써도 됐을 것 같지만 깔끔하게 보이고싶어서 함수를 써봤다.

함수 내 첫 for 반복문에서 각 자릿수의 P제곱 합을 구하고, 그 값이 이미 배열 안에 있다면

그 값이 마지막 값일 때까지 pop해서 빼낸다.

그리고 그 값이 [-1]의 자리에 있으므로 반복문을 빠져나와서 한번 더 pop했다.

 

​