[백준] 1110번 : 더하기 사이클 - [C++]

 

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

1110번: 더하기 사이클

 

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

 

 

그리 어려운 문제는 아닐 것이다. 조금만 문제를 자세히 살펴보면 쉽게 풀 수 있다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

 

 

문제 원리는 간단하다.

 

1. 1의 자릿수는 10의 자리수가 된다.

2. 각 자릿수의 값을 더한 결과의 1의 자릿수는 1의 자리수가 된다.

3. 위 과정을 통해 얻은 결과가 초기에 주어진 수랑 같을 때 까지 반복한다.

 

이 세 개만 찾아내면 된다. 쉽게 말해 아래 이미지와 같은 원리다.

 

 

 

위 문제 예제처럼 26을 그대로 적용한다면 이렇다.

 

초기값 : 26

loop 1 : 26 -> 2 + 6 = 8 -> 68

loop 2 : 68 -> 6 + 8 = 14 -> 84

loop 3 : 84 -> 8 + 4 = 12 -> 42

loop 4 : 42 -> 4 + 2 = 6 -> 26     ← 초기값 26과 같으므로 break(반복 종료)

 

이렇게 되는 것이다.

 

 

그럼 각 자릿수 연산을 구현하기만 하면 된다.

 

일단 연산의 대상이 되는 수를 N, 그리고 연산을 통해 새로 생성되는 수를 T 라고 정의하고 풀이해보겠다.

 

 

 

가장 먼저 N의 1의 자릿수는 T의 10의 자릿수가 된다.

가장 쉽게 할 수 있는 연산은 N을 10으로 나눈 나머지 값에 10을 곱하면 T의 10의 자릿수가 된다.

 

T = (N % 10) * 10	// T의 10의 자릿수

 

 

 

다음으로 T의 1의 자릿수를 구하기 위해서는 일단, N의 각 자릿수를 더해야 할 것이다.

N의 10의 자릿수는 N / 10 이 될 것이고, 1의 자릿수는 N % 10 이 될 것이다. 그 값들을 더한 뒤, 해당 값의 1의 자릿수를 얻으면 된다.

쉽게 수식으로 보면 아래와 같다.

 

(N / 10) + (N % 10)	// N의 10의 자릿수와 1의 자릿수를 더함

T = ((N / 10) + (N % 10)) % 10	// 더한 값의 1의 자릿수가 T의 1의 자릿수가 됨

 

 

 

자, 그러면 T의 1의 자릿수와 10의 자릿수를 구했으니, 위 두 수식을 합치면 다음과 같아진다.

 

 

// (T의 10의 자릿수)         (T의 1의 자릿수)
//  _____________    _________________________
T = (N % 10) * 10 + ((N / 10) + (N % 10)) % 10

 

 

 

 

이제 위를 토대로 반복문으로 작성한다면 다음과 같다.

 

int init = input();
int N = init;
int count = 0;

while(true) {
	// N에 대해 반복하므로 연산된 값도 N으로 덮어써준다.
	N = (N % 10) * 10 + ((N / 10) + (N % 10)) % 10;

	count++;	// 사이클 수 증가
	
	if(N == init) {	// 초기값과 같아진다면 break;
		break;
	}
}

 

 

위와 같은 방식으로 작성해주면 된다.

 

왜 while(N != init) 이 아닌 while(true)로 두고, 연산 후 if(N == init) 조건식 구조로 하는가하면 일단 N과 init은 맨 처음은 무조건 같은 값을 갖고있다.

 

최소한 1회 연산을 시작해야지 사이클이 시작되는 것이다. 만약 while(N != init)으로 한다면 어떤 수를 입력하던 맨 처음 init과 N은 같은 값을 갖고있기 때문에 while문 블럭이 실행되지 않는다.

 

그렇기 때문에 N에 대해 연산을 한 뒤 그 값이 N과 init이 같은지를 판별해야하는 것이다.

하지만, 위와같이 하면 조금 보기도 불편하고 조건식이 매 반복마다 while문 조건식과 if문 조건식 이렇게 총 두 번 실행된다. 그러면 while문 안에 조건식으로 좀 더 간략하게 짤 순 없을까?

 

가능하다.  만약 while문에 대해 조금의 지식이 있다면 while문 대신 do-while문으로 하는 방식도 있다. 일단, do-while문을 설명하기 전에 코드를 먼저 보도록 하자.

 

 

int init = input();
int N = init;
int count = 0;

do {
	// N에 대해 반복하므로 연산된 값도 N으로 덮어써준다.
	N = (N % 10) * 10 + ((N / 10) + (N % 10)) % 10;

	count++;	// 사이클 수 증가
	
} while(N != init);	// 초기값과 같지 않다면 계속 loop

 

 

위와 같이 작성해줄 수 있다.

 

while문과 do-while문의 차이는 무엇인가?

while문은 조건검사 후 while 블럭 실행이고, do-while문은 블럭 실행 후 조건 검사다.

 

 

// 조건식 검사 -> true = 블럭 실행 , false = loop 종료 
while(조건식) {
	...
}

// 블럭 실행 -> 조건식 검사 -> true = 다음 loop로 블럭 실행, false = loop 종료
do {
	...
} while(조건식);

 

 

즉, 쉽게 말해 조건을 먼저 검사하고 블럭을 실행 할 것인지, 블럭을 먼저 실행한 뒤 조건을 검사할 것인지의 차이다.

 

 

 

이를 토대로 이제 출력과 몇 가지 소스만 만들어주면 된다.

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

이전 포스팅과 여타 다를 바 없이 입출력을 달리하여 풀이하도록 하겠다.

알고리즘은 이왕 배운 거 do-while문으로 통일하여 풀이하고자 한다.

 

 

 

 

1. 기본 입출력

2. 향상 된 입출력

 

 

 

 

---

• 풀이

- 방법 1 : [기본 입출력]

 

#include <iostream>

using namespace std;

int main(int argc, const char *argv[]) {

	int init, N;
	int count = 0;
	cin >> init;

	N = init;

	do {
		// N에 대해 반복하므로 연산된 값도 N으로 덮어써준다.
		N = (N % 10) * 10 + ((N / 10) + (N % 10)) % 10;

		count++; // 사이클 수 증가
	} while (init != N);

	cout << count;	// 사이클 수 출력
	return 0;
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

알고리즘도 크게 차이 없이 그대로 갖고와서 별 다를게 없을 것이다.

 

 

 

---

- 방법 2 : [향상 된 입출력]

 

 

 

입력 방법을 향상시킨 방법이다. 이 번의 경우는 입력과 출력이 번갈아가며 나오지는 않으므로 cin.tie() 는 써줄 필요는 없을 것이다.

 

 

 

 

#include <iostream>

using namespace std;

int main(int argc, const char *argv[]) {

	ios_base::sync_with_stdio(false);

	int init, N;
	int count = 0;
	cin >> init;

	N = init;

	do {
		// N에 대해 반복하므로 연산된 값도 N으로 덮어써준다.
		N = (N % 10) * 10 + ((N / 10) + (N % 10)) % 10;

		count++; // 사이클 수 증가
	} while (init != N);

	cout << count;	// 사이클 수 출력
	return 0;
}

 

 

 

성능 차이가 있으려나 싶긴 하지만, 앞으로 위와 같은 방법을 많이 쓰게 될 것이니 계속 익숙해지기 위해 두 가지 방식을 설명하기로 했다.

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

 

채점 번호 : 30714494  -  방법 2 : 향상 된 입출력

채점 번호 : 30714494  -  방법 1 : 기본 입출력

 

 

 

음.. 성능차이는 없는 걸로,,,

 

 

---

• 정리

 

이 번 문제는 그렇게 어려운 문제는 아니였다.

while문 카테고리 문제가 적기도 하고, 모든 while문 구조는 for문으로도 변환이 가능하기 때문에 그리 어렵진 않다. 만약 do-while문에 대해 몰랐다면 한 번 검색해서 찾아보시는 것도 많은 도움이 될 것이다.

 

혹여 어렵거나 이해가 되지 않는 부분이 있다면 언제든 댓글 남겨주시길 바란다.