[백준 c++] 1105 팔 (실1)

📌 문제

숫자 L과 R이 있을 때, 숫자 두 개 사이에 8을 가장 최소로 가지는 숫자의 8의 개수를 출력하는 문제다.

 

먼저 생각나는 방법은 L부터 R까지의 숫자들의 자리수를 하나씩 구해서 최소 값을 구한다고 생각할 수도 있다.

하지만 명심할 점은 굳이 우리가 하나씩 확인할 필요가 없이 생각 하나로 바꿀 수 있다는 점이다.

 

첫번째, L과 R의 자리수에서 분명히 공통된 부분이 있을 것이다. 

공통된 자리수에 있는 8의 개수는 L과 R의 사이에 있는 숫자들도 무조건 가지기 때문에 앞으로 셀 필요가 없다는 것.

 

두번재, 우리는 8이라는 숫자를 쓰는 것을 피하는 것이다.

그러므로 L과 R사이의 숫자 사이에 8 이에외의 자리수를 가지는 숫자가 분명히 존재한다면 굳이 8을 쓸 필요가 없다는 것이다. 

이런 점을 고려했을 때 Brute Force로 계산하지 않고 최소 값을 구할 수 있다.

 

[사담]

개인적으로 실버1 난이도 치고 쉬운 편이다... 

코딩테스트에도 이런 문제가 나왔으면 하지만 한 번도 그런 적은 없었다.....ㅎ...^^

요즘 추세가 다 구현, DFS, BFS 이쪽이 많이 나와서..ㅠ

이렇게 머리 굴려서 푸는 문제(?)는 없애는 추세다. 둘다 빡세기 때문에....

 

💻 정답 코드

#include <iostream>

using namespace std;

int main()
{
    int L, R; cin >> L >> R;
    
    
    //8의 최소값인 문제.
    //결국 내가 8을 어쩔수 없이 품어야하는 경우는 
    //두 개의 숫자 사이에 공통된 숫자가 될 경우임.
    //특히나
    
    int lowNum[10];
    int highNum[10];
    
    //숫자 쪼개기
    int low = L;
    int Lidx = 0;
    
    while(low != 0){
        //가장 아래 자리수를 배열에 저장
        lowNum[Lidx++] = low % 10;
        low /= 10;
    }
    
    int high = R;
    int Ridx = 0;
    
    while(high != 0){
        //가장 아래 자리수를 배열에 저장
        highNum[Ridx++] = high % 10;
        high /= 10;
    }
    
    //둘이 자리수가 다를 경우, 무조건 0
    if(Lidx != Ridx){
        cout << 0 << endl;
        return 0;
    }
    
    int max = Lidx;
    
    int cnt = 0;
    
    //같은 숫자가 몇 개인지 확인
    for(int i = max - 1; i >=0 ; i--){
        
        //숫자가 같을 경우
        if(lowNum[i] == highNum[i]){
            
            // 그 숫자가 8일 경우
            if(lowNum[i] == 8) cnt++;
        }
        
        //아닐 경우는 볼 필요도 없이 패스
        else break;
    }
    
    cout << cnt << endl;
    
    return 0;
}