[BAEKJOON] 1100. 더하기 사이클

Title :
1100. 더하기 사이클

Question :

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의 사이클 길이를 출력한다.

Example :
Input 1 :
26
Output 1 :
4

Input 2 :
55
Output 2 :
3

Input 3 :
1
Ouput 3 :
60

Input 4 :
0
Output 4 :
1

Limited - time :
2초
Limited - space :
256 MB

전체 FlowChart :

cl_solution.h

#include<iostream>
#include <map>
class cl_solution{
	public :
		int fn_run(int num);
};

cl_solution.cpp

int cl_solution::fn_run(int num){
	if (num >= 0 && num <= 99) {
		int first_num = 0, second_num = 0, cnt=0, result=0;
		std::map<int,int> save_nums;

		while (1) {			
			first_num = num%10;
			second_num = num / 10;
			result = first_num + second_num;
			num = (first_num*10) + (result % 10);
			if (save_nums.find(num) != save_nums.end())
				break;
			save_nums.insert(std::pair<int,int>(num, cnt));
			cnt++;
		}
		return cnt;
	}
	
	return -1;
}

main.cpp

#include"cl_solution.h"

int main() {
	cl_solution sol;
	int num = 0;
	std::cin >> num;
	std::cout<<sol.fn_run(num);
	return 0;

}

 

코드&문제 분석 :

문제를 살펴 보면 크게 3가지로 조건, 숫자 하나를 두 개로 나누기, 오른쪽 수 더하기로 볼 수 있으며

문제의 반복 횟수를 바로 알 수 없으므로 무한 반복문을 사용할 수 있다. 또한 사이클 더하기 이므로 

반복 횟수를  체크하며 나간다. 

사용 변수 : 

변수 명	설명
num	사용자 숫자 혹은 이전 새로운수
first_num	사용자 숫자 혹은 이전 새로운수의 오른쪽을 저장
second_num	사용자 숫자 혹은 이전 새로운수의 왼쪽을 저장
cnt	사이클 체크
save_nums	중복 데이터 체크를 위한 map<int,int> 변수
result	두 수를 더한 결과

 

1. 조건

0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다.

이에 관한 FlowChart는 아래와 같이 작성 하였다.

문제에서 조건을 벗아나는 경우 어떠한 결과를 반영하라고 하지 않았으므로 필자는 -1을 반환하였다.

소스 코드는 아래와 같다.

int cl_solution::fn_run(int num){
	if (num >= 0 && num <= 99) {
		문제 해결
	}
	
	return -1;
}

 

2. 문제 해결 -1 (숫자 하나를 두 개로 나누기)

먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다.

숫자를 두개로 나누어 사용 하겠다는 것이며, 이 수를 더하여 숫자 하나를 만든다는 것을 알 수 있다.

따라서 저장 할 수 있는 아래와 같은 변수들과 사용자가 입력한 num을 사용하고자했다.

int first_num = 0, second_num = 0, result=0;

숫자를 두개로 나누기 위해서는 %연산과 /연산을 이용하였다.

int first_num = 0, second_num = 0, cnt=0, result=0;
first_num = num%10;
second_num = num / 10;
result = first_num + second_num;

 

3. 문재해결 -2 (오른쪽 수 더하기)

주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다.

위에서 더해진 수 result의 1의 자리 숫자와 사용자가 입력한 숫자(혹은 이전 새로운수)의 오른쪽을 더해서 새로운 수를 만든다고 한다.

num = (first_num*10) + (result % 10);
if (save_nums.find(num) != save_nums.end())
	break;
save_nums.insert(std::pair<int,int>(num, cnt));

4. 카운트 반환

카운트 반환을 통하여 문제 해결 종료.

while (1) {			
	문제 해결-1,2
    cnt ++;
}
return cnt;

 

Result :

BaekJoon :

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

1110번: 더하기 사이클

 

Github :

https://github.com/Anchangun/BaekJoon/tree/main/Question/Print/1110.%20%EB%8D%94%ED%95%98%EA%B8%B0%20%EC%82%AC%EC%9D%B4%ED%81%B4