백준 문제풀이 : (1105) 팔 - c/c++

문제 주소 : https://www.acmicpc.net/problem/1105

1105번: 팔

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	512 MB	SILVER 1	수학 / 그리디 알고리즘

 

 

문제

---

 

 

풀이

---

L과 R 사이에 있는 수 중, 8이 가장 적게 들어있는 수에 8이라는 숫자가 몇 번 들어있는 지를 구하는 문제입니다. 

 

L과 R은 다음과 같은 두 가지 경우로 입력될 수 있습니다.

 

1. L과 R의 자릿수가 다르다. (ex. L:20, R:300)

2. L과 R의 자릿수가 같다. (ex. 20, 30)

 

먼저 1번 상황인 경우, L과 R 사이에 있는 8이 가장 적게 들어있는 수의 8의 개수는 0개입니다. 

자릿수가 다른 두 수 사이에는 8이 포함되어있지 않은 10의 제곱수가 무조건 하나 이상 걸쳐있기 때문입니다. 

 

따라서 8의 개수는 L과 R의 자릿수가 같은 경우에서만 계산해주면 됩니다. 

 

L과 R의 자릿수가 같은 경우, 두 수 사이의 8의 개수를 구하는 풀이 방법은 다음과 같습니다. 8의 개수는 변수 result에 저장합니다.

1. L과 R의 맨 앞자리부터 비교해갑니다. 

2. 비교한 두 수가 모두 8이라면 result+1을, 두 수가 8은 아니지만 같은 숫자라면 result 변화 없이 다음 루프로 넘어갑니다.

3. 비교한 두 수가 아예 다른 수라면 루프를 종료하고 result를 출력합니다. 

 

예를 들어 L은 '12890', R은 '12898'일 경우, 앞 12까지는 같은 수이지만 8이 아니기 때문에 result의 변화가 없습니다. 

세 번째 자리는 L과 R이 모두 8이기 때문에 result를 1 상승시킨 후 다음 루프(다음 자리수 검사)로 넘어갑니다. 

 

네 번째 자리에서 L은 9, R은 8로 두 수가 다릅니다. 이 경우, L의 뒤 두자리 90과 R의 뒤 두 자리 98 사이에는 무조건 8이 아닌 수가 포함되어있을 수 밖에 없습니다. 

 

따라서 자릿수를 비교하는 루프를 탈출하여, 이전까지 카운트된 result가 문제의 정답이 됩니다.

 

 

코드작성

---

#include <iostream>

using namespace std;

int getCipher (int num) { //자릿수(10의 제곱수 단위로) 구하는 함수
    int cipher=1;
    while (num>10) {
        num/=10;
        cipher*=10;
    }
    return cipher;
}   

int isEqual(int l, int r, int cp) { //두 수 비교해서 앞 자리 같은지
    if (l/cp == r/cp) {
        if ((l/cp)%10==8) return 1; //두 수가 같으면서 8이면 1 리턴
        else return 2; // 두 수가 같지만 8이 아니라면 2 리턴
    } else return 0; // 두 수가 아예 다르다면 0 리턴
} 

int main() {
    int l, r, cipher=0, result=0;
    scanf("%d %d", &l, &r);
    
    cipher=getCipher(l);
    if (cipher==getCipher(r)) {
        for (int i = 0 ; i<cipher ; cipher/=10) {
            int flag = isEqual(l, r, cipher);
            if (flag==1) { 
                result++;
            } else if (flag==2) continue;
            else break;
        }
    }
    
    printf("%d", result);
}

 

 

END.