[C++] 백준 1105번 팔

1. 문제이해

https://www.acmicpc.net/problem/1105

1105번: 팔

 

L보다 크거나 같고, R보다 작거나 같은 자연수들 중

8의 개수가 가장 적은 숫자의 8의 개수를 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

L보다 크거나 같고, R보다 작거나 같은 자연수들 중

8의 개수가 가장 적은 숫자의 8의 개수(min)를 구하는 문제이다.

아래 예제풀이를 통해 자세히 알아보자.

 

1. 두 수의 자릿수가 틀린 경우

: 무조건 두 수의 중간에 10, 100, 1000 ...  과 같은 숫자가 포함되므로,

min = 0 이다.

 

2. 두 수의 자릿수가 같은 경우 (1)

: 두 수의 앞자리부터 탐색을 시작한다.

앞자리부터 탐색 시, 해당 자릿수의 값이 같고, 해당 값이 8이면 min 값을 증가해준다.

 

3. 두 수의 자릿수가 같은 경우 (2)

: 위 문제와 같이 두 수의 앞자리부터 탐색을 시작한다.

앞자리부터 탐색 시, 해당 자릿수의 값이 같고, 해당 값이 8이면 min 값을 증가해준다.

단, 해당 자릿수의 값이 같지 않는 경우를 만나면,

8이 아닌 다른 값이 존재 가능하므로, 그 즉시 탐색 종료.

(그 이후의 자릿수 또한 자동으로 8이 아닌 수가 존재 가능하다.

예를 들어 70과 80을 보게 되면, 첫째 자리수인 7, 8이 다르므로 그 즉시 탑색을 종료한다.

뒤의 자리인 0, 0 이 같아도, 앞 자리 숫자가 다르므로 충분히 다른 숫자가 존재 가능하기 때문.)

 

 

위와 같이 각기 다른 3가지 경우를 통해 도출한 알고리즘은 아래와 같다.

 

1. 두 수의 자릿수가 다르다면, min = 0

 

2. 두 수의 자릿수가 같다면, 앞 자릿수부터 탐색

➡ 해당 자릿수의 값이 같고, 8 이면 min값 증가

➡ 해당 자릿수의 값이 같지 않으면 즉시 탐색 종료

 

위 알고리즘을 통해 풀이한 소스코드는 아래와 같다.

 

 

 

3. 소스코드

#include <iostream>
#include <string>
using namespace std;

int main() {
	string L, R;
	int min = 0;
	
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> L >> R;

	// 1. 두 숫자의 자릿수가 다른 경우 : 값 = 0
	if (L.size() != R.size()) {
		cout << 0;
	}

	// 2. 두 숫자의 자릿수가 같은 경우
	else {
		for (int i = 0; i < L.size(); i++) {
			// 해당 자리의 값이 같지 않으면 for문 종료
			if (L[i] != R[i]) {
				break;
			}

			// 해당 자리의 숫자가 8로 같은 경우
			// 8이 무조건 하나 있는 것이므로 min++
			if (L[i] == R[i] && L[i] == '8') {
				min++;
			}
		}

		cout << min;

	}

	return 0;
}

L과 R을 문자열 형태로 입력받고,

2. 문제풀이에서 도출한 알고리즘에 따라 코드를 작성했다.

 

1. 두 수의 자릿수가 다른 경우에는 즉시 min = 0 값을 출력해주고,

2. 두 수의 자릿수가 같은 경우 for문을 통해 탐색 후 

➡ 해당 자릿수의 값이 8로 같으면 min값 증가

➡ 해당 자릿수의 값이 같지 않으면 즉시 탐색 종료 해주었다.

 

 

---

하나하나 앞에서부터 8의 갯수를 찾고 비교하려니 시간초과가 발생했던 문제였다.

시간제한이 2초면 상당히 긴건데, 아무래도 숫자의 범위가 크다보니

해당 방법은 시간초과가 발생했던 것 같다..

덕분에 효율적인 알고리즘을 공부하고 찾아내긴 했지만,

알고리즘을 생각해내는 과정은 언제나 어려운 것 같다..😥