전체 글
-
[Algo Rhythm🕺💃] BOJ 1759 - 암호 만들기Algo Rhythm🕺💃/BOJ 2021. 6. 30. 19:52
💫문제 분석 암호가 구성되는 서로 다른 알파벳 소문자의 개수를 $l$, 암호로 사용했을 법한 문자의 개수를 $c\ (3 \le l \le c \le 15)$라고 하자. 암호를 이루기 위해서는 다음과 같은 두 조건을 만족해야 한다. 최소한 한 개 이상의 모음(a, e, i, o, u)로 이루어져 있다. 최소한 두 개 이상의 자음들로 이루어져 있다. 암호를 이루는 알파벳들은 증가하는 순서로 배열되어 있다. 암호로 사용했을 법한 문자들을 하나의 vertex로 보자. 그렇다면 이 문제는 $c$개의 vertex들 중 앞서 언급한 조건들을 만족하여 $l$개의 vertex들을 선택하는 backtracking 문제로 이해할 수 있다. 🔥문제 풀이 먼저 암호로 사용했을 법한 문자들을 저장한 배열 $alphabets$을 ..
-
[Algo Rhythm🕺💃] BOJ 18290 - NM과 K(1)Algo Rhythm🕺💃/BOJ 2021. 6. 30. 17:41
💫문제 분석 크기가 $n \times m\ (1 \le n,\ m \le 10)$인 격자판을 $g$라고 하자. $g$의 각 칸에는 정수가 하나씩 들어있는데 인접한 칸들을 제외하고 $k\ (1 \le k \le \min (4, n \times m))$개의 칸을 선택하여 각 칸에 들어있는 모든 수들을 더할 때 나올 수 있는 값들 중 최댓값을 구해야 한다. $g$의 각 칸을 하나의 vertex라고 생각해보자. 그렇다면 이 문제는 $n \times m$개의 vertex들 중에서 인접한 칸들을 제외하고 $k$개의 vertex를 선택할 때 얻을 수 있는 최댓값을 구하는 backtracking 문제로 이해할 수 있다. 🔥문제 풀이 $n \times m$개의 칸 중 $k$개의 칸을 선택할 때 한 가지 조건은 이미 선택..
-
[Algo Rhythm🕺💃] BOJ 9095 - 1, 2, 3 더하기Algo Rhythm🕺💃/BOJ 2021. 6. 29. 00:06
💫문제 분석 테스트 케이스의 개수를 $t$, 각 테스트 케이스마다 주어지는 정수를 $n (1 \le n \lt 11)$이라고 하자. 그리고 $n$을 $1,\ 2, \ 3$의 합으로 나타내는 방법의 수를 $f(n)$이라고 하자. 각 테스트케이스마다 $f(n)$을 출력해야 하며, 합을 나타낼 때는 수를 1개 이상 사용해야 한다. $f(n)$은 1부터 차례대로 아래와 같다. 이때 파란색 동그라미로 표시된 수들을 관찰하면 분명히 연쇄적인 관계가 있다는 것을 알 수 있다. 따라서 이 문제는 그 '연쇄적인 관계'를 이용하여 해결할 수 있다. 🔥문제 풀이 앞서 언급한 연쇄적인 관계는 다음과 같다. $\begin{matrix} f(i) &=& \sum_{j = 1}^3 g(i, j) & (1\le i\lt 11, i ..
-
[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 6588 - 골드바흐의 추측Algo Rhythm🕺💃/BOJ 2021. 6. 23. 17:45
문제 분석 이 문제는 4보다 큰 어떤 짝수 $x (6 \le x \le 10^6)$가 두 홀수인 소수 $a, b (a \le b)$의 합으로 나타낼 수 있는지 판별하는 문제이다. 이때 주의할 점은 골드바흐의 추측은 $10^{18}$ 이하에서 참임이 확인되었기 때문에 두 홀수 소수의 합으로 나타내지 못 하는 경우는 생각하지 않아도 된다는 것이다. 문제 풀이 1. '소수 판별 알고리즘' 응용 주어진 $x$에 대하여 $a$의 가능한 최소값인 3부터 $x - a$인 $b$가 2보다 크지 않을 때까지 $a, b$ 모두 소수인지 판별한다. 만약 모두 소수라면 $x = a + b$를 출력한 뒤 반복문을 탈출하고 그렇지 않다면 $a$를 2씩 증가하고 위 과정을 반복한다. 이때 2씩 증가하는 이유는 짝수는 절대 소수가 ..