[C++] [BFS / DFS] 백준 2331 번 문제 풀이

 

문제

 

 

 

 

DFS / BFS 와 그리디 두 가지 방법으로 풀었는데 DFS / BFS를 사람들이 일반적으로 많이 사용한다.

시간적으로는 DFS / BFS 가 효율적이고 , 메모리 사용량으로 보면 그리디가 좀 더 효율적이다.

 

첫 번째 풀이 : DFS / BFS

A 의 최대는 9999 , P의 최대는 5

나올 수 있는 가장 큰 값은 : 9의 5승 * 4 = 236196

 

 

Code

 

// BaekJoon 2331
// Title : 반복 수열
// URL : https://www.acmicpc.net/problem/2331

#include <iostream>
#include <cmath>

using namespace std;

#define MAX_NUM 236196

int visit[MAX_NUM];
int P;
int answer = 0;

void DFS(int A){
    int origin = A;
    int next = 0;

    visit[A-1]++;

    while(A > 0){
        next += (int)pow( A % 10 , P);
        A /= 10;
    }

    if(visit[next-1] == 2) return ;
     
    DFS(next);

    if(visit[origin-1] == 1) answer++;

}

int main(int argc, char** argv){
    int A , num;

    cin >> A >> P;

    DFS(A);

    cout << answer;
}

 

 

두 번째 풀이 : 그리디 알고리즘

 

 

Data structure로는 deque를 사용하였다.

반복 구간을 algorithm의 find 함수로 찾아서 iterator를 통해 갯수를 구했다.

 

 

Code

 

// BaekJoon 2331
// Title : 반복 수열
// URL : https://www.acmicpc.net/problem/2331

#include <iostream>
#include <cmath>
#include <deque>
#include <algorithm>

using namespace std;

int next_num(int D , int P){
    int total = 0;
    
    while(D > 0){ 
        total += pow( (D % 10) , P);
        D /= 10;
    }
    return total;
}

int main(int argc , char** argv){
    int A , P , num;
    deque<int> dq;
    deque<int> ::iterator iter;

    cin >> A >> P;

    dq.push_back(A);

    while(1){

        A = next_num(A , P);
        iter = find(dq.begin() , dq.end() , A);
        if(iter != dq.end()){
            num = iter - dq.begin();
            break;
        }

        dq.push_back(A);
    }

    cout << num;

}

 

 

https://www.acmicpc.net/problem/2331

2331번: 반복수열