[BOJ] 백준 1110번 : 더하기 사이클 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/1110

1110번: 더하기 사이클

문제

0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다. 다음 예를 보자.

26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = 12이다. 새로운 수는 42이다. 4+2 = 6이다. 새로운 수는 26이다.

위의 예는 4번만에 원래 수로 돌아올 수 있다. 따라서 26의 사이클의 길이는 4이다.

N이 주어졌을 때, N의 사이클의 길이를 구하는 프로그램을 작성하시오.

 

풀이

수학적인 지식을 활용하는 문제였습니다. 특히, 수의 자릿수를 따질 때는 몫과 나머지 연산을 쓰는 경우가 많은데 이 문제도 예외는 아니였습니다. 다만, 실수의 여지가 있어서 문제를 꼼꼼히 읽으시는 것이 중요했습니다.

제가 생각한 로직은 다음과 같습니다.

1. x의 십의 자리를 q, 일의 자리를 r이라고 할 때, q + r을 한 sum을 구한다.

2. x = r * 10 + sum % 10으로 초기화해 준다.

3. x와 N이 다시 같아지는 순간까지 위 2가지 작업을 반복한다.

여기서 의문이 하나 생기실 수 있습니다. '문제에서는 분명, 일의 자리일 경우 앞에 0을 붙여서 두 자리로 만든다고 했는데, 이것에 대해서는 왜 처리를 하지 않았는가?'와 같이 말이죠.

그것은 아래 2번째 예제에서 설명해 드리도록 하겠습니다.

 

예제

1. N : 26

x = N에 저장을 한 뒤, 시작합니다.

x는 현재 26으로 일의자리가 아니므로 각각의 자리를 십의 자리와 일의 자리로 분할합니다.

q = 26 / 10 = 2, r = 26 % 10 = 6으로 어렵지 않게 구할 수 있습니다. 그리고 이 두 개를 합한 sum = 2 + 6 = 8 입니다.

이제, x를 r * 10 + sum % 10한 값인 68로 새롭게 초기화를 해 줍니다.

(여기서 r * 10을 하는 이유는 r를 새로운 십의 자리로 만들기 위함이고, sum % 10을 하는 이유는 문제에서 sum의 가장 오른쪽 자리를 이어붙여아한다고 되어있기때문입니다.)

다시, 68은 q = 6, r= 8로 쪼갤 수 있고, sum = 14 이므로, x = 8 * 10 + 14 % 10 = 80 + 4 = 84가 됩니다.

84는 q = 8, r = 4로 쪼갤 수 있고, sum = 12이므로, x = 4 * 10 + 12 % 10 = 40 + 2 = 42가 됩니다.

마지막으로, 42는 q = 4, r = 2로 쪼갤 수 있고, sum = 6이므로 x = 2 * 10 + 6 % 10 = 20 + 6 = 26으로, 이것은 x와 N이 같아지는 순간입니다. 따라서, 총 4번 만에 26으로 다시 돌아오는 것을 알 수 있습니다.

 

2. N : 55

x = N에 저장을 한 뒤, 시작합니다.

전반적인 로직은 위와 동일합니다. 다만, 일의 자리가 나오는 경우를 알아보겠습니다.

일단, 55는 q = 5, r = 5로 쪼갤 수 있고, sum = 10이므로, x = 5 * 10 + 10 % 10 = 50 + 0 = 50이 됩니다.

그리고, 50은 q = 5, r = 0으로 쪼갤 수 있고, sum = 5이므로, x = 0 * 10 + 5 % 10 = 0 + 5 = 5가 됩니다.

여기서, 5를 주목하시면 되겠습니다.

문제에서는 5 앞에 0을 붙임으로써 두 자리로 만든다고 했는데, 사실 제가 위에서 세운 수식에는 전혀 영향이 가질 않습니다. 05라는 숫자는 존재하지 않겠지만, 있다고 가정했을 때 q = 0, r = 5가 되고, sum = 5이므로 결과적으로 x = 5 * 10 + 5 = 55가 됩니다.

0을 붙이지 않는 5에 경우도, q = 5 / 10 = 0, r = 5 % 10 = 5가 되고, sum = 0 + 5 = 5이므로 마찬가지로 x = 5 * 10 + 5 % 10 = 50 + 5 = 55가 됩니다.

어차피 새로운 숫자를 만들 때는 q가 중요한 것이 아니라, r과 sum을 이어붙여서 만들어야하기 때문에 일의 자리에 경우도 똑같이 처리해도 상관이 없습니다.

따라서 55 -> 50 -> 5 -> 55 로 총 3번만에 55로 다시 돌아오는 것을 알 수 있습니다.

 

아래는 위의 내용을 기반으로 작성한 소스코드입니다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
 
        int x = N; // x에 N을 저장.
        int cnt = 0; // 반복한 횟수.
        while (true) {
            int q = x / 10; // x의 십의 자리
            int r = x % 10; // x의 일의 자리
 
            int sum = q + r;
 
            x = r * 10 + sum % 10; // r과 sum의 가장 오른쪽 값을 더한다.
            cnt++;
 
            if (x == N) { // x와 N이 같아지는 순간 반복문을 종료.
                break;
            }
        }
 
        bw.write(cnt + "\n");
 
        bw.flush();
        bw.close();
        br.close();
    }
 
}

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.