Awkward Digits( BOJ 5929 )

문제 : https://www.acmicpc.net/problem/5929

5929번: Awkward Digits

 

문제 파악하기

베시가 잘못 바꾼 2진수와 3진수를 파악하여 원래 숫자를 찾는 문제입니다. 베시는 항상 1자리 숫자를 잘못 쓴다는 사실을 파악한다면 모든 자리 숫자를 1개씩 바꿔 조합하여 문제를 해결할 수 있습니다.

 

문제 해결하기

베시는 항상 1자리씩 숫자를 잘못 쓴다고 했습니다. 그렇기에 우리는 베시가 쓴 2진수와 3진수 숫자에서 1개씩 바꾼 다음, 10진수로 변환하여 비교하면 됩니다. 만약 2진수와 3진수에서 나온 숫자가 동일하다면 우리가 찾던 원래 숫자이기 때문에 탐색을 종료하고 해당 숫자를 출력하면 됩니다.

 

소스코드

#include <stdio.h>
#define NMAX 35
 
char inp2[NMAX], inp3[NMAX];
 
int len[2];
int num2[NMAX], num3[NMAX];
 
int N2, N3, ret;
 
char convert(char c) {
    if(c == '0') return '1';
    else return '0';
}
 
int getNum(int num[NMAX], int k) {
    int ret=0;
 
    for(int i=0;i<len[k-2];i++) ret = ret*k + num[i];
 
    return ret;
}
 
int main() {
    // 입력(2진수)
    scanf("%s", inp2);
    for(int i=0;inp2[i]!='\0';i++) {
        if(inp2[i] == '0') num2[i] = 0;
        else num2[i] = 1;
 
        len[0]++;
    }
 
    // 입력(3진수)
    scanf("%s", inp3);
    for(int i=0;inp3[i]!='\0';i++) {
        if(inp3[i] == '0') num3[i] = 0;
        else num3[i] = inp3[i]-'0';
 
        len[1]++;
    }
 
 
    for(int i=0;i<len[0];i++) {
        // 2진수 숫자 1개 바꾸기
        num2[i] = (num2[i]+1)%2;
 
 
        for(int j=0;j<len[1];j++) {
            for(int k=1;k<=3;k++) {
                // 3진수 숫자 1개 바꾸기
                num3[j] = (num3[j]+1)%3;
 
                N2 = getNum(num2, 2);
                N3 = getNum(num3, 3);
 
                if(N2 == N3) ret = N2;
            }
        }
 
        num2[i] = (num2[i]+1)%2;
    }
 
    // 출력
    printf("%d", ret);
}

후기

간단한 브루트포스 문제입니다. 배열과 반복문으로 해결할 수 있는 문제이기 때문에 PS를 시작하는 사람에게 추천하는 문제라고 생각합니다.