BOJ 2331

그래프를 위한 vector의 크기를 전역변수로 잡으려고 하는데, vertex의 최대 개수가 주어지지 않아서... 어떻게 해야하지 생각하다가 일단 풀이먼저 하자는 생각으로 있었는데...
입력값이 9999가 최대이고, 지수가 5가 최대이므로...
9^5 * 4 = 59049 * 4 =236196..... 헐
음 그래프를 평소처럼 잡으면 안되려나.. 일단 엄청난 공간 낭비가 예상되는데...
2^5 + 3^5 + 6^5 + 1^5 + 9^5 + 6^5 = 32 + 243 + 7776 + 1 + 59049 + 7776 = 74877

74877 -> 50421 + 1024 + 32768 = 84213
84213 -> 243 + 1 + 32 + 1024 + 32768 = 34068...음 일단 236196 보다 커지지는 않을 수도 있을 것 같긴하지만..음 확실치 않아보인다.

그래서 그래프 표현방식을 edge를 표현 해주는 방식((예), a[9999]=236196, a[236196]=9999, 9999 vertex와 236196vertex의 연결이다)으로 하면 안될 것 같다는 생각을... 음 풀이를 일단 봐야겠다.

문제 풀어봐야겠다. 

백준님의 풀이를 보고 알게됨...
일단 내가 풀어본 그래프 문제들 처럼 그래프를 위한 자료구조를 할당할 필요가 없다. 
어차피 한방향으로 꼬리 물듯이 이어지는 그래프 모양이기 때문에
방문했는지 아닌지를 체크하는 check 배열만 있으면 된다. 
그리고 check배열에는 0 아니면 이 숫자가 몇번째인지 정보를 넣어주고(구하고자 하는 것이 반복되기 전 vertex의 개수이므로...) ...

그런데 왜 check배열을 1000,000만큼 선언했는지 잘 모르겠다.
한번 34068부터 해봐야지
34068 -> 3^5 + 4^5 + 0 + 6^5 + 8^5 = 243 + 1024 + 0 + 7776 + 32768 = 41811
아 근데 난 프로그래밍을 배운 사람인데 왜 이걸 손으로 하고 앉아있지...
프로그램을 짜서 돌려보겠다.

돌려보니... 



 
일단은 84213으로 다시 돌아가는것과..
음 그리고 236196이 가장 크네..
하지만 모든 경우의 수에서.. 예를들어 9998로 시작하면 236196보다 더 큰 수가 나올수 있다든가... 어떻게 예상하지..한번 질문해봐야겠다...