수학
-
[Algo Rhythm🕺💃] BOJ 1748 - 수 이어쓰기 1Algo Rhythm🕺💃/BOJ 2021. 6. 28. 19:17
문제 분석 1️⃣. 나의 풀이 자연수 $i (1 \le i \le 8)$, $num \in [10^{i - 1}, 10^i)$를 만족하는 자연수 $num$, $num$에 따라 더해지는 글자 수, 그리고 $num$의 개수를 정리한 표는 아래와 같다. 입력으로 주어진 $n (1 \le n \le 10^8)$의 자릿수를 $\alpha$라고 하고 1부터 $n$까지 이어 쓸 때 만들어지는 새로운 수의 자릿수를 $f(n)$이라고 할 때, $f(n)$을 구하는 것이 이 문제의 핵심이다. 2️⃣. 다른 분의 풀이 (깔끔✨) 입력으로 주어진 $n (1 \le n \le 10^8)$ 이하인 모든 자연수들에 대하여 각 자리수 별로 나눠서 생각해보자. 1의 자리가 있는 수는 1부터 $n$까지 총 $(n - 1 + 1)$개이다..
-
[Algo Rhythm🕺💃] BOJ 17425 - 약수의 합Algo Rhythm🕺💃/BOJ 2021. 6. 24. 21:43
문제 분석 약수의 성질 중 하나는 두 자연수 $a, b$에 대하여 $a$가 $b$의 배수이면 $b$는 $a$의 약수(들) 중 하나라는 것이다. 그리고 이 문제는 자연수 $n(1 \le n \le 10^6)$을 입력할 때 $g(n)$을 출력할 것을 요구한다. 이때 $g(n)$은 아래와 같은 수식으로 정의할 수 있다. $g(n)= \begin{cases} g(n - 1) + f(n) & n \gt 1\\ 1 & n = 1 \end{cases}$ 앞서 말한 두 가지를 종합할 때 이 문제는 약수의 성질을 이용하여 모든 $n$에 대하여 $g(n)$을 구하여 저장한 다음 테스트케이스로 $n$에 속하는 자연수 $a$가 들어올 때마다 $g(a)$를 출력하는 문제로 이해할 수 있다. 문제 풀이 1. $g(n)$을 저장하..
-
[Algo Rhythm🕺💃] BOJ 17427 - 약수의 합 2Algo Rhythm🕺💃/BOJ 2021. 6. 24. 01:42
문제 분석 입력으로 주어지는 자연수를 $n (1 \le n \le 10^6)$ 그리고 $n$보다 작거나 같은 자연수를 $i$라고 하자. 자연수 $a$가 자연수 $b$로 나누어 떨어진다면 즉, $a$가 $b$의 배수라면 $b$는 $a$의 약수이다. 따라서, 이 문제는 $i$에 속하는 한 자연수의 배수의 개수와 그 자연수를 곱한 값들을 더하여 $g(n) = \sum_{i=1}^n f(i)$을 구하는 문제로 이해할 수 있다. 문제 풀이 $i$를 1부터 $n$까지 반복하여 $i$의 배수의 개수와 $i$를 곱한 값들을 더한다. 이때 $i$의 배수는 $n/i$개이다. 그리고 $i > n/2$일 때 $n$보다 작은 자연수들 중 $i$의 배수는 $i$ 자기 자신뿐이다. 따라서 그 경우에는 $i$만 더한다. 복잡도 분석..
-
[Algo Rhythm🕺💃] BOJ 4375 - 1Algo Rhythm🕺💃/BOJ 2021. 6. 23. 21:55
문제 분석 1로만 이루어진 한 정수를 $x$, 2와 5로 나누어 떨어지지 않는 정수를 $n (1 \le n \le 10^5)$이라고 하자. 이 정수의 오른쪽 끝에 1을 붙이기 위해서는 정수의 자릿수를 한 자리 올린 후 1을 더하면 된다. 즉, $10 \times x + 1$을 하면 된다. 하지만 overflow가 발생할 수 있기 때문에 계속해서 오른쪽 끝에 1을 붙일 수 없다. 다행히도 문제에서 요구하는 것은 $x$ 자체가 아니라 $x \mod n == 0$을 만족할 때의 자릿수이다. 따라서, 중요한 것은 $x$가 아니라 $x \mod n$이라는 것을 알 수 있다. 그래서 정수의 오른쪽 끝에 1을 붙일 때 $x = 10 \times x + 1$이 아닌 $x = (10 \times x + 1) \mod n..
-
[Algo Rhythm🕺💃]BOJ 13458 - 시험감독Algo Rhythm🕺💃/BOJ 2021. 3. 9. 16:53
문제 분석 시험장의 개수를 N(1 ≤ N ≤ 1,000,000), i번째 시험장에 있는 응시자의 수를 Ai(1 ≤ Ai ≤ 1,000,000) , 총감독관과 부감독관이 한 시험장에서 감시할 수 있는 응시자의 수를 각각 B, C(1 ≤ B, C ≤ 1,000,000)라고 하자. 그리고 i번째 시험장에 들어가야 하는 총감독관과 부감독관의 수를 각각 $n\_main_i$, $n\_sub_i$라고 하자. 총감독관은 각 시험장에 무조건 한 명 들어가야 하고 부감독관은 없거나 여러 명 있어도 된다. 따라서 i번째 시험장에서 필요한 감독관 수의 최솟값은 아래 부등식을 만족하는 가장 작은 $n\_sub_i$를 구하는 것과 같다. $B\ +\ C \times n\_sub_i\ \ge A_i$ 이를 통해 우리가 최종적으로..