[백준] 22251번: 빌런 호석

 

구현 문제이다.

 

 

 

 

 

 

 

 

 

 

처음 생각했던 접근방식

 

이 문제는 예전에 코딩테스트를 볼 때 거의 후반부에 위치했던 문제 유형과 매우 유사했다.

당시에는 시간도 부족했고 어떻게 풀어야겠다는 방법을 찾기 어려워서 문제를 못풀었지만, 지금은 시간이 많으니 도전해보았다.

 

복잡하게 생긴 문제일수록 단순한 접근이 좋다는 것을 느꼈고, 숫자를 어떻게 컴퓨터가 이해할 수 있는 코드로 표현할까 생각한 결과,

 

인덱스 0~6까지의 길이가 7인 string으로 표현해보기로 했다.

즉, "1110111"은 0, "0010010"은 1, "1011101"은 2로 표현할 수 있다. 

string 배열인 nums 에 각각의 숫자 표현식을 저장하고, 실제 멈춰있는 X층과 비교하여 다르면 1씩 추가하는 방식으로 구현했다.

그러다가 잠깐 막혔을 때가 각 자릿수를 비교하는 것이었는데, 해당 자릿수는 %10, 그 다음 자릿수는 /10을 하면 되었다.

 

 

 

 

 

 

합당한 접근방식

#include <iostream>
#include <string>
 
using namespace std;
 
int N, K, P, X; //N 최대 숫자
                //K 자릿수
                //P 최대 P개 반전
                //X 대상 숫자
 
string nums[10] = {
    "1110111", //0
    "0010010", //1
    "1011101", //2
    "1011011", //3
    "0111010", //4
    "1101011", //5
    "1101111", //6
    "1010010", //7
    "1111111", //8
    "1111011" //9
};
 
int CheckDiff(int num){
    int cnt = 0;
    int tmpX = X;
    for(int i=0; i<K; i++){
        int digitX = tmpX % 10;
        int digitNum = num % 10;
        for(int j=0; j<7; j++){ //각 인덱스가 다른경우 +1
            if(nums[digitX][j] != nums[digitNum][j]) cnt++;
        }
        tmpX /= 10;
        num /= 10;
    }
    return cnt;
}
 
int main(){
    
    cin >> N >> K >> P >> X;
    int ret = 0;
    for(int i=1; i<=N; i++){ 
        int cnt = CheckDiff(i);
        if(cnt && cnt <= P){
            ret++;
        }
    }
    cout << ret;
 
 
    return 0;
}

 

숫자를 문자열로 표현하는 것과 각 자릿수를 비교하는 방법이 이 문제의 핵심이었다.