์ƒ์„ธ ์ปจํ…์ธ 

๋ณธ๋ฌธ ์ œ๋ชฉ

[๋ฐฑ์ค€(BOJ)] 2331๋ฒˆ: ๋ฐ˜๋ณต์ˆ˜์—ด (DFS/BFS, C++)

PROGRAMMING/Algorithm

by koharin 2021. 2. 26. 14:16

๋ณธ๋ฌธ

728x90
๋ฐ˜์‘ํ˜•

๐Ÿ“ ๋ฌธ์ œํ’€์ด ๊ณผ์ •


์ด๋ ‡๊ฒŒ 37, 58, 89, 145, 42, 20, 4, 16์ด ๋ฐ˜๋ณต๋œ๋‹ค.

2๋ฒˆ ์ด์ƒ ๋ฐ˜๋ณต๋˜๊ณ , 3๋ฒˆ์งธ๋กœ ๋ฐ˜๋ณต๋˜๊ธฐ ์‹œ์ž‘ํ•˜๋ฉด ๊ทธ๋•Œ ๋ฆฌํ„ดํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  visited์—์„œ 1์ธ ๊ฒƒ์€ ๋ฐ˜๋ณต๋˜์ง€ ์•Š๋Š” ๊ฒƒ์ด๋ฏ€๋กœ ์นด์šดํŒ…ํ•ด์„œ ๋‹ต์„ ๊ตฌํ•œ๋‹ค.

๊ฐ single digit์€ ์ด์ „ ์ˆซ์ž์—์„œ % 10์„ ํ•˜๊ณ , (์ด์ „ ์ˆซ์ž/ 10) % 10์œผ๋กœ ๋ฐ˜๋ณตํ•ด์„œ make_sum ํ•จ์ˆ˜์—์„œ ๋‹ค์Œ ์ˆซ์ž(next)๋ฅผ ๊ตฌํ•ด์คฌ๋‹ค.

์ฃผ์˜ํ•ด์•ผ ํ•  ์ ์€, ์ œ๊ณฑ๊ทผ์„ pow๋กœ ๊ตฌํ•  ๋•Œ int ํ˜•์œผ๋กœ ํ˜•๋ณ€ํ™˜์„ ํ•ด์ค˜์•ผ ๋งž์•˜๋‹ค๋Š” ๊ฒƒ์„ ๋ฐ›์„ ์ˆ˜ ์žˆ๋‹ค.

 

๋ฐ˜๋ก€

์ž…๋ ฅ1]
57 2

์ถœ๋ ฅ1]
4

์ž…๋ ฅ2]
153 3

์ถœ๋ ฅ2]
0

์ž…๋ ฅ3]
58 2

์ถœ๋ ฅ3]
0

 

 

๐Ÿ’ป C++ ์ œ์ถœ์ฝ”๋“œ


#include <stdio.h>
#include <deque>
#include <string>
#include <cmath>
using namespace std;

int make_num(int start, int P){
    int temp=start;
    int next=0;
    
    for(int i=1; i<=to_string(start).length(); i++){
        next += (int)pow(temp % 10, P);
        temp /= 10;
    }
    return next;
}

void DFS(int start, deque<int> *D, int *P, int *visited){
    if(++visited[start] == 3) return;
    int next = make_num(start, *P);
    DFS(next, D, P, visited);
}

int main(){
    int A, P, count=0; 
    scanf("%d %d", &A, &P);
    deque<int> D;
    int visited[300000 + 1]={0,};

    D[1] = A;
    DFS(D[1], &D, &P, visited);
    for(int n: visited){
        if(n == 1) count++;
    }
    printf("%d", count);
}

 

 

๐Ÿ‘ ๊ฒฐ๊ณผ


728x90
๋ฐ˜์‘ํ˜•

๊ด€๋ จ๊ธ€ ๋”๋ณด๊ธฐ