[백준] 1105 팔

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

1105번: 팔

초기에 L 부터 R까지 하나씩 올려가면서 확인을 하려고 구현을 했더니 시간초과가 걸렸다. 다양한 방식으로 수정을 해봤지만 시간초과...

결국 질문을 확인했고, 거기에 나온 로직때로 구현했더니 성공

 

[로직]

1. L 과 R의 자리수가 같은지 판별

1-1. 다르다면 답은 0

1-2. 같다면 2.

 

2. L 과 R 의 각 자리수를 큰 자리수부터 비교한다.

2-1. 같다면 answer++;

2-2. 다르다면 break;

 

왜 그런지 확인해보자.

1-1 의 경우)

88, 888 은 자리수가 각각 2, 3이다. 

88 ~ 888 중에는 자리수가 바뀜으로 8이 존재하지 않는 수가 당연히 존재한다 (ex. 677)

 

2 의 경우)

8889 8899

앞자리수부터 비교를 시작한다.

첫째자리수가 둘다 8 임으로 answer = 1이 된다.

두번째 자리수 또한 8 임으로 answer = 2가 된다. 

세번째 자리수가 각각 8, 9 로 다르다. 그러므로 break;

그런데, 왜 break를 하는가?

8889 8890 8891 ~ 8899 까지 생각해보면, 8890 으로 세번째 자리수가 9로 바뀔 수 있다.

고로, 그 아래 모든 자리수들이 8이 아닌 수가 배치될 수 있으므로 그 이상 비교할 필요가 없는 것이다. (ex. 8893)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

string L, R;

int main() {

	cin >> L >> R;

	if(L.size() != R.size()) {
		printf("0\n");
		return 0;
	}
	int answer = 0;
	for(int i=0; i<L.size(); i++) {

		if(L[i] == R[i] && R[i] == '8')
			answer++;
		else if(L[i] != R[i])
			break;
	}
	printf("%d\n", answer);
	return 0;
}