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

DFS적 성격만 띄고 있는 문제이다. 그래프 문제라 하기에는…

memoization으로 반복되는 수들을 잘 체크만 해주면 되는 문제이다.

C++ 코드

#include <iostream>
#define max 300000    //주의! 9의 5승이 4자리일때, 23만이 넘어감. 범위 조심!

int count_arr[max];

void DFS(int a, int p) {
    int new_a = 0;

    while (a > 0) {    // 새로운 수 만들기
        int left = a % 10;
        int leftSquare = 1;
        for (int i = 0; i < p; i++) leftSquare *= left;
        new_a += leftSquare;
        a /= 10;
    }

    count_arr[new_a]++;
    if (count_arr[new_a] > 2) return;    //2회까지 반복되는 수열 확인 후, return 
    DFS(new_a, p);
}


int main() {
    int A = 0, P = 0;

    scanf("%d %d", &A, &P);

    count_arr[A] ++;
    DFS(A, P);
    int count = 0;
    for (int i = 0; i < max; i++)
        if (count_arr[i] == 1) count++;

    printf("%d", count);



}

C# 코드

using System;
using static System.Console;

class Program
{
    static int[] count_arr = new int[300000];

    static void DFS(int a, int p)
    {
        double new_a = 0;      //Math.Pow(제곱수 구하는 내장함수) 사용하기 위해선, double 타입으로 받아야 함.

        while (a > 0)
        {    //새로운 수 생성
            int left = a % 10;
            new_a += Math.Pow(left, p);
            a /= 10;
        }
        int x = (int)new_a;    //배열이 int 이므로, 다시 int로 형변환....ㅜ

        count_arr[x]++;
        if (count_arr[x] > 2) return;
        DFS(x, p);
    }

    public static void Main(string[] args)
    {
        string[] s = ReadLine().Split(' ');
        int A = int.Parse(s[0]);
        int P = int.Parse(s[1]);

        count_arr[A]++;
        DFS(A, P);
        int count = 0;
        for (int i = 0; i < count_arr.Length; i++)
            if (count_arr[i] == 1) count++;

        Write($"{count}");


    }
}

Java 코드

import java.util.*;

class Main {
  static int[] count_arr = new int[300000];

  static void DFS(int a, int p){
    double new_a = 0;
    while( a> 0){
      double left = a %10;
      new_a += Math.pow(left, p);
      a /=10;
    }

    int x = (int) new_a;
    count_arr[x]++;
    if(count_arr[x] > 2) return;
    DFS(x,p);
  
  }
  
  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    int A = s.nextInt(); 
    int P = s.nextInt();

    count_arr[A]++;
    DFS(A, P);
    int count = 0;
    for(int i =0 ; i< count_arr.length; i++)
      if(count_arr[i] == 1) count++;

    System.out.println(count);
  }
}

Kotlin 코드

import java.util.*

var count_arr = Array<Int>(300000) {0}

fun DFS(a: Int, p: Int){        //주의! 코를린 함수의 매개변수는 무조건 val!
    var x = a                   //a값 변경을 위해 var변수 생성
    var new_a = 0
    while(x > 0){
        var left = x % 10
        var leftsquare = 1
        for(i in 1..p) leftsquare *= left       //pow함수 쓰지 않고 for문으로 직접 제곱수 구함
        new_a += leftsquare
        x /= 10
    }

    count_arr[new_a]++                          //새로운 수. 배열에 체크
    if(count_arr[new_a] > 2) return
    DFS(new_a, p)
}

fun main(args: Array<String>) {         //var - 변경가능, val - 변경불가 변수
    val s = Scanner(System.`in`)
    val A = s.nextInt(); val P = s.nextInt()

    count_arr[A]++
    DFS(A, P);
    var count = 0
    for(i in count_arr)
        if(i == 1) count++

    print("${count}")


}

Python 코드

import sys
sys.setrecursionlimit(300000)       #파이썬은 재귀를 1000회만 기본으로 함으로, 제한을 늘려놓기

count_arr = [0 for _ in range(300000)]

def DFS(a,  p):
    new_a = 0
    while a > 0:
        new_a += (a % 10) ** p      # 파이썬은 제곱도 operater(**)가 존재
        a //= 10            # !주의 : 파이썬은 'float형'이 될 수 있는 /(한 개짜리 나누기) 와 'int형'으로 몫만 나오는 //(두 개짜리 나누기) 존재

    count_arr[new_a]+=1
    if count_arr[new_a] > 2 : return
    DFS(new_a, p)

A, P = map(int, input().split())
count_arr[A] += 1
DFS(A,P)
count = 0
for i in count_arr:
    if i == 1: count += 1
print(count)