Post List

[BOJ] 백준 2331 반복수열

날짜:

[BOJ] 백준 2331 반복수열


나는 이 문제를 단순 큐의 성질을 사용하여 풀었다.
큐에 후보들을 전부 넣고, 새로운 후보가 나왔을 때 기존 후보 큐에서 하나씩 꺼내서 확인하는 방법을 취했다.
다른 사람들이 푼 코드를 보니, visited배열을 사용해서 이미 나왔던 것이 있다면 그 인덱스를 계산해서 출력하는 형태를 취한것 같다.

소스코드 : 

#include 
#include 
#include 
#include 
#include 
using namespace std;

// 수열을 계산하는 함수
int GetSequence(string str, int myPow) {
 int size = str.length();
 int res = 0;
 for (int i = 0; i < size; i++) {
  res += pow(str[i] - 48, myPow);
 }
 return res;
}
// 정수를 문자열로 변환하는 함수
string MyItos(int num) {
 string str = "";
 int idx = 10;
 stack st;
 while (num > 0) {
  st.push((num % idx) + 48);
  num /= idx;
 }
 while (!st.empty()) {
  str += st.top();
  st.pop();
 }
 return str;
}

int main() {
 string d1;
 int dn;
 cin >> d1 >> dn;
 queue myQueue;
 myQueue.push(stoi(d1));
 int find = 0;
 bool isFound = false;
 while (true) {
  int tmp = GetSequence(d1, dn);
  int front = myQueue.front();
  int length = myQueue.size();
  // 현재 큐에서 겹치는게 있는지 다 찾아봄.
  for (int i = 0; i < length; i++) {
   if (tmp == myQueue.front()) {
    // 찾음
    find = i;
       isFound = true;
    break;
   }
   else {
    int tmpFront = myQueue.front();
    myQueue.pop();
    myQueue.push(tmpFront);
    
   }
  }
  if (isFound) break;
  myQueue.push(tmp);
  d1 = MyItos(tmp);
 }
 cout << find  << endl;

}

댓글

댓글 쓰기