문제적남자 131회 - 로꾸꺼

문제

어떤 숫자를 반전해 그 두 개의 숫자를 더한 값을 다시 반전해 더하는 과정을 3번 반복할 때 나올 수 있는 4자리 숫자 중 가장 큰 회문 숫자는?

(단, 모두 같은 숫자 X)

먼저 회문(Palindrome)은 앞으로 읽으나, 뒤로 읽으나 같은 단어나 문장을 말하는데, 

회문 숫자라 함은 '회문의 성질을 지닌 숫자', 즉 앞으로 읽으나 뒤로 읽으나 그 값이 같은 수를 말한다. 

예를 들어서 '9999', '7447', '818', '565676565' 등등이 있을 것이다.

문제 해결에서 고려해야 할 것은 다음과 같다.

1) 길이제한: 결과값은 4자리 수이므로 (1000<=결과값<=9999)를 만족해야 한다.

이때, 조건에서 4자리 수가 모두 같은 숫자로 이루어질 수 없다고 했으므로 (1001<=결과값<=9889)이다.

2) 회문판별: a==d, b==c를 동시에 만족하면 회문이다. 

3) 회문의 제한: '4자리 수의 결과 값이 모두 같은 숫자로 이뤄질 수 없다'라고 하므로 '9999', '8888'과 같은 숫자들은 나올 수 없다. 

결과값의 각 자릿수를 a(천의 자리), b(백의 자리), c(십의 자리), d(일의 자리)라고 하면, (a==b==c==d)는 False가 되어야 한다.

그런데, 회문에서 a==d, b==c이므로 (a==b)가 False인지만 체크해주기만 하면 된다. 

4) 숫자 하나와 그 숫자를 반전한 숫자를 더할 때 자릿수 문제:

어떤 수 n과 n을 반전한 수를 더할 때, n의 각 자릿수를 a(천의 자리), b(백의 자리), c(십의 자리), d(일의 자리)라고 하므로 

(n+n을 반전한 수)=n+(d*1000+c*100+b*10+a)로 구할 수 있다. 

그러나, n이 3자리 수일 때 문제가 발생한다. 예를 들어서 n=100일때, n이 3자리 수이므로 a=0, b=1, c=0, d=0이다.

100을 반전하면 001, 즉 1이 되어야 정상적인 결과이지만 위 식에 따르면 (d*1000+c*100+b*10+a)=0+0+1*10+0=10이 된다.

따라서 n이 1000보다 작을 때는 (n+n을 반전한 수)=n+(d*100+c*10+b)로 계산해야 한다. 

그렇게 되면 n=100일때 a=0, b=1, c=0, d=0이고 (d*100+c*10+b)=0+0+1=1으로 제대로 나온다.

물론 최대값을 만드는 처음 수가 3자리 이하일 리는 없겠지만 그래도 재미삼아 만들어 보자.

2자리일 때 반전한 수는 (d*10+c)이고, 1자리일 때는 반전할 거 없다! 크크

어차피 최대값을 찾는 게 목적이니 코드는 3자리수일 때까지만 처리해 두겠다.

문제적남자에서는 타일러가 665로 9119를 만들었고, 박경이 724로 9559를 만들어 문제를 해결했다.

그런데 두 분 다 게싱(Guessing)으로 하셨다...! ㄷㄷ 고려대의 힘 

코드 1

#include <stdio.h>
int main(){
    int max=0;
    for(int n=100; n<=999; n++){
        int sum=n; 
        int a, b, c, d;
        a/*천의 자리*/=sum/1000; 
        b/*백의 자리*/=sum/100%10;
        c/*십의 자리*/=sum/10%10;
        d/*일의 자리*/=sum%10;
        if(sum>999) sum+=d*1000+c*100+b*10+a;
        else sum+=d*100+c*10+b;
        for(int i=0; i<3; i++){
            a/*천의 자리*/=sum/1000; 
            b/*백의 자리*/=sum/100%10;
            c/*십의 자리*/=sum/10%10;
            d/*일의 자리*/=sum%10;
            if(sum>999) sum+=d*1000+c*100+b*10+a;
            else sum+=d*100+c*10+b;
        }
        a/*천의 자리*/=sum/1000; 
        b/*백의 자리*/=sum/100%10;
        c/*십의 자리*/=sum/10%10;
        d/*일의 자리*/=sum%10;
        if(sum>9889||sum<1001) continue;
        else if(a!=d || b!=c) continue;
        else if(a==b) continue;
        else{
            printf("n:%d sum:%d\n", n, sum, a, b, c, d);
            if(sum>max) max=sum;
        }
    }
    printf("\nmax: %d", max);
}

역시 9559로 답이 잘 나온다. 

그러고 보니 타일러의 '처음 수'는 665였는데, 최대값과 같이 9559의 결과가 나오는 수는 670, 고작 5 차이였다..ㅠㅠ

코드 2

#include <stdio.h>
int main(){
    int max=0;
    for(int n=100; n<=999; n++){
        int sum=n; 
        int a, b, c, d;
        for(int i=0; i<4; i++){
            a/*천의 자리*/=sum/1000; 
            b/*백의 자리*/=sum/100%10;
            c/*십의 자리*/=sum/10%10;
            d/*일의 자리*/=sum%10;
            if(sum>999) sum+=d*1000+c*100+b*10+a;
            else sum+=d*100+c*10+b;
        }
        a/*천의 자리*/=sum/1000; 
        b/*백의 자리*/=sum/100%10;
        c/*십의 자리*/=sum/10%10;
        d/*일의 자리*/=sum%10;
        if(sum>9889||sum<1001) continue;
        else if(a!=d || b!=c) continue;
        else if(a==b) continue;
        else{
            printf("n:%d sum:%d\n", n, sum, a, b, c, d);
            if(sum>max) max=sum;
        }
    }
    printf("\nmax: %d", max);
}