문제 ✍🏻 :: [1110번] 더하기 사이클
(초록색 글자 클릭 시 문제로 이동)
.JPG)
.JPG)
정수 N을 입룍 받는다. 입력 받은 N의 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만든다. 원래의 수로 돌아오는 사이클의 길이를 구하는 프로그램을 작성하시오.
알고리즘 (접근방법) 💻
10952번 A+B-5번과 마찬가지로 테스트케이스가 없다. 즉, 반복하는 횟수를 모르기 때문에 for문이 아니라 while문을 사용해야 한다.
for문 : 반복 횟수를 정확히 알 때
while문 : 반복 조건을 설정할 때
조건을 설정하여 초기에 입력한 수와 같은 수가 나오면 반복이 종료되도록 설정한다.
조건을 어떻게 설정해야 할 것인가가 관건이다.
1번째 시도: 계산을 10의 자리 수와 1의 자리수로 쪼갬
➡ 결과 : 🚨"컴파일에러" + "시간초과"🚨
2번째 시도 : 여러 변수 사용 없이 한 줄에 담을 수 있도록 변경
➡ 결과 : ✨정상 작동!
자세한 코드는 아래에서 설명하겠다!
💡1번째 시도💡
1번째 시도는 오답이었다. 코드는 다음과 같다.
#include <iostream>
using namespace std;
int main()
{
int N, a, b;
int cnt = 0;
int sum = 0;
cin >> N;
a = N / 10; //10의 자리 수
b = N % 10; //1의 자리 수
//합이 N과 다르면 계속 반복
while (sum != N) {
//1의 자리수와 10의 자리 수 더하기
sum = a + b;
a = b; //10의 자리 수에 1을 대입
b = sum % 10; //
cnt = cnt + 1; //사이클의 길이 +1
}
cout << cnt;
return 0;
}
==> 이러면 프로그램이 실행되지 않을 뿐만 아니라, 백준 사이트에 제출하면 '시간초과'로 오답처리된다.
어떻게 답을 수정해야 하는 걸까?
💡2번째 시도💡
문제를 하나하나 뜯어서 살펴보자!
- N ( 0 <= N <= 99) 을 입력받는다.
- N의 각 자리의 숫자를 더한다.
- N의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙여 새로운 수를 만든다.
- 2~3번 과정을 반복하고 새로운 수가 원래 수로 돌아오는 사이클의 수를 구한다.
N=26이라 하고, 사이클을 cnt라 하겠다.
| cnt | 각 자리 수 더하기 | 새로운 수 |
|---|---|---|
| 1 | 2 + 6 = 8 | 68 |
| 2 | 6 + 8 = 14 | 84 |
| 3 | 8 + 4 = 12 | 42 |
| 4 | 4 + 2 = 6 | 26 |
26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = 12이다. 새로운 수는 42이다. 4+2 = 6이다. 새로운 수는 26이다.
위의 예는 4번만에 원래 수로 돌아올 수 있다. 따라서 26의 사이클의 길이는 4이다.
.
.
.
이 예시를 보면 각 자리 수를 더한 값이 1의 자리 수에, 그 전 1의 자리 수가 10이 되는 걸 볼 수 있다.
문제 지문을 한 문장 단위로 분석을 통해 코드를 어떻게 작성했는지 설명하겠다.
1. N ( 0 <= N <= 99) 을 입력받는다.
간단하다! cin을 이용하여 정수 N을 입력받는다.
2. N의 각 자리의 숫자를 더한다.
각 자리 수를 더 하려면 /와 % 연산자를 이용한다.
10의 자리 수는 /로 1의 자리 수는 %로 하면 된다.
N = N / 10 + N % 10 //❶
3. N의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙여 새로운 수를 만든다.
① N의 가장 오른쪽 자리 수
➡ 1의 자리 수이므로 %로 구할 수 있다.
N % 10
② 앞에서 구한 합의 가장 오른쪽 자리 수
➡ 합이 두 자리 수가 되면 가장 오른쪽 자리를 구해야 한다. 마찬가지로, %이용한다.
(N / 10 + N % 10) % 10 //앞에 구한 합의 오른쪽 수
③ 이 둘(①,②)을 이어 붙여 새로운 수를 만든다.
➡ 두 수를 더한다. 더할 때, 10의 자리 수에는 10을 곱한다. 10의 자리 수는 ①(N의 가장 오른쪽 자리 수)이다.
N = (N % 10) * 10 + (N / 10 + N % 10) % 10 // ① + ②
4. 2~3번 과정을 반복하고 새로운 수가 원래 수로 돌아오는 사이클의 수를 구한다.
➡ 몇 번 반복 하는지 모르니 while문을 사용한다.
➡ 반복을 수행할 때마다 1씩 더해지는 변수가 필요하다. 이 변수는 선언할 때 0으로 초기화해야 한다.
while (true) { cnt = cnt + 1; N = (N % 10) * 10 + (N / 10 + N % 10) % 10 // ① + ② }
이때, 원래 수와 새로운 수가 같은지 비교를 해야 while문을 종료할 수 있다. 따라서 초기에 원래 수(N)을 다른 변수에 저장해둔다. 이 후, if문을 이용하여 같은지 확인 후, 반복문을 종료한다.
cin >> N; A = N; // while (true) { cnt = cnt + 1; A = (A % 10) * 10 + (A / 10 + A % 10) % 10 // ① + ② if ( N == A ) { //원래 수와 새로운 수가 같은지 비교 break; } }
전체 코드는 다음과 같다.
#include <iostream>
using namespace std;
int main()
{
int N, A;
int cnt = 0; // 사이클을 계산하는 변수. 초기에 0으로 초기화
cin >> N; //N을 입력 받는다.
//나중에 if문으로 같은지 비교하기 위해
//while문 내의 계산을 하기 위한 변수 A에 N의 값을 저장한다.
A = N;
while (true) {
cnt = cnt + 1; //사이클 수 1 증가
A = (A % 10) * 10 + (A / 10 + A % 10) % 10;
if (N == A) { //원래 수와 새로운 수가 같은지 비교
break;
}
}
cout << cnt; //사이클 수를 출력
return 0;
}💡제출결과💡
(입출력 동기화를 해제 하지 않아도 0ms 이어서, 굳이 이 방법을 채택하진 않았다. )
회고 🤔
-
1번째 시도한 방법이 왜 되지 않을까, 어떻게 해야 하는 걸까 며칠을 고민했다. 꼭 쪼개지 않아도 한 줄로 할 수 있을 것 같은데 방법을 잘 모르겠는 느낌이 들었다.
이때 위에 글처럼, 문제를 하나하나 쪼개서 풀었다. 그러다보니 웬걸 생각보다 쉽게 결론이 나왔다. 허무하기도 하고, 뿌듯하기도 하고 이상한 감정이 들었다. 그래서 뒤에 문제를 풀어도 기억에 남는 문제가 될 것 같다. -
이걸 어떻게 또 글로 적을까- 막막했다. 그래도 다 쓰고 나니까 너무 속시원하다.
Reference
