[백준 1110] 더하기 사이클 / 증명

1110번: 더하기 사이클 (acmicpc.net)

1110번: 더하기 사이클

 

문제 요약

a=a/10*10+(a/10+a%10)%10을 계속 반복하여

a의 값이 처음 입력했던 값과 같아질 때의 최소 연산횟수를 구하는 것이다.

 

증명

1. a->b 일때, b에 대한 a은 특정 된다.

 

a가 A*10+B로 이루어져 있을 때 b는 B*10+C로 이루어져 있다.

C는 (A+B)%10이다. (현재 B와 C를 알고 있는 상태, A는 모름)

 

A값에 따른 C의 값은 C(x)=(x+B)%10 (0<=x<=9, x는 정수)로 알 수 있고,

C(x)는 직선의 형태로 0<=C(x)<=9 라는 조건을 만족하는 것을 알 수 있다. (1대1 대응)

 

그러면 C와 B의 값을 알고 있다면 A값을 특정할 수 있으니

b에 대한 a는 특정이 가능하다.

 

2. 어떤 a는 a->b->c->d->b....으로 무한 루프가 형성된다.

 

위에서 말한 논제 1에 어긋난다.

b로 들어가기 전의 값은 a로 특정 되었는데 a!=d인 d가 나오니 말이 안되는거

 

코드

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, A, P=0; cin>>n; A=n;

    do
    {
        int a, b; P++;
        a=A/10; b=A%10;
        A=b*10+(a+b)%10;
    }while(A!=n);

    cout<<P;

    return 0;
}