[문제 풀이] 백준 1110번 더하기 사이클 JAVA

본 문제는 주어진 수를 10의 자리와 1의 자리로 나누어 더한 후 1의 자리였던 숫자와 더한 숫자의 1의 자리를 더하는 것을 반복하여 원래 주어진 수로 돌아오기까지 걸린 횟수를 구하는 문제이다.

 

이 문제를 처음 접하고 문제 그대로 주어진 숫자를 10으로 나누고 10의 자리와 1의 자리를 더한 값도 10으로 나누기를 반복하여 횟수를 측정하는 식으로 접근해 보았다.

 

작성한 코드는 아래와 같다.

import java.util.Scanner;
public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        System.out.print(cycle(n));
    }
    public static int cycle(int n){
        int start=n;
        int cnt=0;
        while(true){
            int a=n/10;
            int b=n%10;
            int c=a+b;
            cnt++;
            n=b*10+c%10;
            if(n==start){return cnt;}
        }
    }
}

본 코드의 시간복잡도는 O(60) = O(1)이다.

왜냐하면 n이 최대 60 사이클이 될수 있는데 이는 최악의 상황에 반복문이 60번 돌아갈 수 있음을 의미하기 때문이다.