[집중 문제] it 취업을 위한 알고리즘 문제 풀이 입문 (With C/C++) 30. 3의 개수는?(large)

[기억할 내용들]

그냥 완전 수학 이용해서 푸는 문제였다.
문제 풀이에 사용되는 변수는 cur, left, right, cnt, k, res 이다.
각 자리수를 기준으로 해서 res 에 값을 추가하는 식으로 문제를 해결해야 한다.

left 를 구하는 공식: left = n / (k * 10)

cur 를 구하는 공식: cur = (n / k) % 10

right 를 구하는 공식: right = n % k

<입력이 5367 일 때>

일의 자리수가 3인 숫자의 개수를 구하자
1. 일의 자리수를 기준으로 할 때는 left 가 536, cur 가 7, right 가 0, k 가 1 이다.
2. cur 값이 3보다 크므로 000 부터 536 까지 모두 포함된다.
3. 000 부터 536 일 때까지 총 왼쪽에 있는 수의 개수는 537 개이다. 일의 자리수 오른쪽으로는 아무것도 올 수 없으므로 537 에 1 인 k 를 곱해주면 일의 자리수가 3인 숫자의 개수를 구할 수 있다.
4. 식으로 정리하면 (left + 1) * k
십의 자리수가 3인 숫자의 개수를 구하자
1. 십의 자리수를 기준으로 할 때는 left 가 53, cur 가 6, right 가 7, k 가 10 이다.
2. cur 값이 3보다 크므로 00 부터 53 까지 모두 포함된다.
3. 00 부터 53 일 때까지 총 왼쪽에 있는 수의 개수는 54개이다. 십의 자리수 오른쪽으로는 0 ~ 9 까지의 숫자가 올 수 있으므로 총 10개의 수가 올 수 있다. 즉, 54 개 모두 10개의 수를 가질 수 있으므로 이 둘을 곱하면 540 으로 십의 자리수가 3인 숫자의 개수를 구할수 있다.
4. 식으로 정리하면 (left + 1) * k
백의 자리수가 3인 숫자의 개수를 구하자
1. 백의 자리수를 기준으로 할 때는 left 가 5, cur 가 3, right 가 67, k 가 100 이다.
2. cur 값이 3과 같으므로 일단 0 부터 4까지 포함된다.
3. 0 부터 4 일 때까지 총 왼쪽에 있는 수의 개수는 5개이다. 백의 자리수 오른쪽으로는 십의 자리수, 일의 자리수가 있고 이는 각각 10개 (0~9) 의 수가 올 수 있으므로 총 100 개의 수가 올 수 있다. 즉, 5개 모두 100개의 수를 가질 수 있으므로 이 둘을 곱하면 500 이다.
4. right 가 67 이라고 했다. 53으로 시작하는 수는 00 부터 67 까지 갈 수 있으므로 총 68개의 수를 가진다.
5. 즉, 3번과 4번에서 구한 개수를 합치면 568 로 백의 자리수가 3인 숫자의 개수를 구할 수 있다.
6. 식으로 정리하면 (left * k) + (right + 1)

백의 자리수가 3인데 cur 값이 3보다 작은 수의 숫자의 개수를 구하자.
1. 공식이 아직 두개밖에 안 나와서 임의로 n 의 값을 5267 로 바꿔서 해보겠다.
2. 백의 자리수를 기준으로 할 때는 left 가 5, cur 가 2, right 가 67, k 가 100 이다.
3. cur 값이 3보다 작으므로 일단 0 부터 4까지 포함된다.
4. 0 부터 4 일 때까지 총 왼쪽에 있는 수의 개수는 5개이다. 백의 자리수 오른쪽으로는 십의 자리수, 일의 자리수가 있고 이는 각각 10개 (0~9) 의 수가 올 수 있으므로 총 100 개의 수가 올 수 있다. 즉, 5개 모두 100개의 수를 가질 수 있으므로 이 둘을 곱하면 500 이다.
5. cur 값이 3보다 작으므로 52 로 시작하는 수의 개수는 고려하지 않아도 된다.
6. 즉 500 이 백의 자리수가 3인 숫자의 개수이다.
7. 식으로 정리하면 (left * k)

left	cur	right	k
536	7	0	1
53	6	7	10
5	3	67	100
0	5	367	1000

[강의 코드]

#include <iostream>
#include <stdio.h>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;

	int cur=0, left=-1, right=0, cnt = 0, k = 1, res = 0;
	while (left != 0) {
		left = n / (k * 10);
		cur = (n / k) % 10;
		right = n % k;

		if (cur < 3) {
			res += left * k;
		}
		else if (cur > 3) {
			res += (left + 1) * k;
		}
		else {
			res += (left * k) + (right + 1);
		}
		k *= 10;
	}
	cout << res << "\n";

	return 0;
}

[의견]

풀이 방법을 모르겠어서 결국 강의를 보고 풀었다. 이 문제가 강의 문제 중에서 어려운 편에 속하는 문제라고 한다. 흠.. 계속 풀다보면 나아질 거라 믿는다.. 열심히 해보자..

티스토리툴바