[백준 BOJ] 11170번 0의 개수 (C++/cpp)

문제 설명

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

11170번: 0의 개수

 

접근 방법 - 브루트포스 알고리즘을 이용한 수학 문제

백준의 11170번 문제는 브루트포스 알고리즘을 활용하여 해결해야 하는 수학적 사고력 문제이다.

해당 문제는, 각 테스트 케이스의 입력값 범위 속 숫자들에 대해 출현하는 0의 개수를 출력해야 하는 문제이다.

브루트포스 알고리즘이란 모든 경우의 수를 감안하여 해답을 얻어내는 알고리즘을 뜻한다.

이 개념이 어색하다면, 해당 블로그에 브루트포스 알고리즘을 검색하여 이와 관련된 다른 글도 확인해보길 바란다.

그래도 해당 문제는 다른 브루트포스 알고리즘 문제들에 비해선 난이도가 많이 양호한 편인 것...

필자의 경우엔 해당 알고리즘을 아래처럼 응용하여 해결해보았다. 해결에 어려움을 겪고 있다면 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 테스트 케이스의 수(n)를 입력받는다.

 

2) 각 테스트 케이스에 대해, 두 숫자(a, b)를 입력받는다.

 

3) 0의 개수를 카운팅할 변수 num을 0으로 초기화하여 선언한다.

 

4) a에서부터 b만큼 반복문을 실행하여 아래의 연산을 취한다. (0의 개수를 구하는 연산 과정을 실행)

(현재 탐색값이 0인 경우엔 예외적으로 두어, num에 1을 더한 뒤 다른 연산을 취하지 않고 다음 과정을 실행한다.)

- 다른 반복문을 실행하여 0의 개수를 카운팅한다.

(ex) 탐색값이 201인 경우,

k가 1인 경우, 201 % (1*10) / 1 = 1 -> 카운팅되지 않음

k가 10인 경우, 201 % (10*10) / 10 = 0 -> 카운팅됨 (num에 1 추가)

k가 100인 경우, 201 % (100*10) / 100 = 2 -> 카운팅되지 않음

 

5) 4)의 연산이 끝났다면, 최종적으로 저장된 num의 값을 출력한다.

 

6) 2) ~ 5)의 과정을 n의 크기만큼 실행한 뒤, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 11170번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		int num = 0;
		for (int j = a; j <= b; j++) {
			if (j == 0) { num++; continue; }
			for (int k = 1; k < j; k *= 10) {
				if (j % (k * 10) / k == 0) { num++; }
			}
		}
		cout << num << endl;
	}
}

 

제출 결과

(2022.04.28 백준 11170번 문제 제출 결과)