BOJ 1110 - 더하기 사이클

문제

BOJ 1110 - 더하기 사이클

0 이상 99 이하의 정수 N이 주어질 때, 십의 자리와 일의 자리를 더한 합의 일의 자리를 원래 수의 일의 자리 뒤에 붙여 새로운 수를 만드는 과정을 반복한다. 원래 수로 돌아올 때까지의 사이클 길이를 구하라.

입력

첫째 줄에 N (0 ≤ N ≤ 99)이 주어진다.

출력

사이클의 길이를 출력한다.

예제

풀이

do-while 루프로 변환을 반복하며 원래 수로 돌아올 때까지 횟수를 센다.

1. 원본 N을 copy에 저장한다
2. 새로운 수 = (일의 자리 * 10) + ((십의 자리 + 일의 자리) % 10)
3. 변환 후 copy와 같아질 때까지 반복하며 카운트를 증가시킨다
4. do-while을 사용하여 최소 1번은 실행되도록 한다

핵심 아이디어: 0~99 범위의 수만 가능하므로 사이클은 반드시 존재하며, do-while로 최초 1회 변환 후 비교를 시작한다.

코드

package day549;
 
import java.io.*;
 
public class Day505BOJ1110더하기사이클 {
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int cnt = 0;
    int copy = N;
 
    do {
      N = ((N % 10) * 10) + (((N / 10) + (N % 10)) % 10);
      cnt++;
    } while (copy != N);
 
    System.out.println(cnt);
  }
}

복잡도

• 시간: O(사이클 길이) (최대 100)
• 공간: O(1)