[★2][백준1110번]더하기 사이클 (JAVA)

[★2][백준1110번]더하기 사이클 (JAVA)

1110번 문제 ☞ https://www.acmicpc.net/problem/1110

난이도 ☞ [★2]

더하기 사이클

• 문제
  • 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의 사이클의 길이를 구하는 프로그램을 작성하시오.
  • 첫째 줄에 N이 주어진다. N은 0보다 크거나 같고, 99보다 작거나 같은 정수이다.

  • 첫째 줄에 N의 사이클 길이를 출력한다.

    예제입력	예제출력
    26	4

    예제입력	예제출력
    55	3

    예제입력	예제출력
    1	60

    예제입력	예제출력
    0	1

    예제입력	예제출력
    71	12

내가 푼 풀이

이번 문제는 받은 숫자의 일의 자리 숫자는 십의 자리로, 받은 숫자의 십의자리와 일의자리 숫자를 더해서 일의 자리로 보내고 이를 반복하면서 입력 받은 숫자의 값으로 다시 돌아올 때까지의 사이클. 즉 횟수를 구하는 문제이다. 천천히 생각해보면 될 것 같다. 아니면 공책에라도 적어서 이해를 해본다면 쉬운 문제이다. 우선 이번 문제를 푸려면 입력 받은 값의 십의 자리수, 일의 자리수를 추출하는 법만 안다면 매우 간단하다. 추출하는 방법은 아래와 같다.

입력 받은 값 바로 다음에 나올 숫자의 십의 자리수를 추출하는 공식은 아래와 같다.

N = (N % 10) * 10

기존 숫자를 10으로 나누고, 나머지 값에 10을 곱해주면 다음 숫자의 십의 자리가 되니 공식은 아래와 같게 되는 것이다. 입력 받은 값 바로 다음에 나올 숫자의 일의 자리수를 추출하는 공식은 아래와 같다.

N = ((N / 10) + (N % 10)) % 10

입력 받은 값 바로 다음에 나올 숫자의 일의 자리수는 입력 받은 값의 십의 자리와 일의 자리 수를 더해 나온 수의 일의 자리를 다음 나올 숫자 일의 자리로 넘겨야하니 공식은 아래와 같다.

위의 코드를 토대로 코드를 작성해보겠습니다. 먼저, Scanner방식입니다.

[ 풀이 1 ]

메모리 : 17728KB
시간 : 208ms

Scanner(while)

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);

		int N = s.nextInt();
		s.close();

		int cnt = 0;
		int C = N;

		while (true) {
			N = ((N % 10) * 10) + (((N / 10) + (N % 10)) % 10);
			cnt++;

			if (C == N) {
				break;
			}   

		}
		System.out.println(cnt);
	}

}

위의 방식은 제일 기본적인 Scanner방식입니다. 다음 풀이는 BufferedReader로 하려했으나 do-while문도 사용해보아야 할 것 같아 풀이 2번은 do-while문으로 풀어보았습니다. BufferedReader방식의 구현을 보고 싶다면 이전 게시물들을 참고하시기 바랍니다.

[ 풀이 2 ]

메모리 : 17656KB
시간 : 204ms

Scanner(do-while)

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);

		int N = s.nextInt();
		s.close();

		int cnt = 0;
		int C = N;

		do {
			N = ((N % 10) * 10) + (((N / 10) + (N % 10)) % 10);
			cnt++;

		} while (C != N);

		System.out.println(cnt);
	}

}

이번 문제는 기본 알고리즘 파악 문제이지 않나 생각이 듭니다.

BKJN 카테고리 내 다른 글 보러가기