ALiNew ALiNew

Algo Rhythm🕺💃/BOJ

• [Algo Rhythm🕺💃] BOJ 16926 - 배열 돌리기 1

  Algo Rhythm🕺💃/BOJ 2021. 8. 14. 21:12

  💫문제 분석 크기가 $n \times m\ (2 \le n, m \le 300)$ 인 배열 $A$를 반시계 방향으로 $r\ (1 \le r \le 1,000)$번 회전한 결과를 출력하기 위해 먼저 $A$를 관찰해보자. $A$를 관찰하면 가장 바깥 층부터 가장 안 층까지 아래 그림과 같이 재귀적인 관계가 있음을 알 수 있다. 또한 가장 바깥 층을 관찰하면 반시계 방향으로 1번 회전할 때 $(1, 1)$에 있는 값을 시작으로 값을 아래로 옮기는 것을 $(n - 1)$번, 오른쪽으로 옮기는 것을 $(m-1)$번 , 위로 옮기는 것을 $(n-1)$번, 왼쪽으로 옮기는 것을 $(m-1)$번 반복해야 한다는 것을 알 수 있다. 🔥문제 풀이 크기가 $n \times m$인 배열 $A$를 반시계 방향으로 1회 회전하는..

  Read More

• [Algo Rhythm🕺💃] BOJ 2225 - 합분해

  Algo Rhythm🕺💃/BOJ 2021. 7. 22. 22:15

  💫문제 분석 입력으로 주어지는 두 정수를 각각 $N,K\ (1\le N,K \le 200)$라고 하자. 그리고 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 $f(N,K)$라고 하자. 마지막으로 N을 만들기 위해 더해지는 K개의 정수들을 순서대로 $I_1, I_2, ..., I_K$라고 하자. $f(N,K)$의 규칙을 파악하기 위해 $f(2, 3)$를 구하는 과정을 분석해보자. $f(2, 3)$은 아래와 같이 6이다. 이때 $I_1$과 나머지 $I_2, I_3$의 관계를 파악해보자. $I_1 = 0$ 일때 $I_2, I_3$를 구하는 것은 $f(2, 2)$을 구하는 것과 같다. (1이 적힌 파란 원으로 표시함) $I_1 = 1$ 일때 $I_2, I_3$를 구하는 것은 $f(1,2)$..

  Read More

• [Algo Rhythm🕺💃] BOJ 1463 - 1로 만들기

  Algo Rhythm🕺💃/BOJ 2021. 7. 22. 00:00

  💫문제 분석 주어진 $n\ (1 \le n \le 10^6)$에 대하여 사용가능한 연산들은 다음과 같다. $op_1 : n \equiv 0 \pmod{3}이면,\ n = n \div 3$ $op_2 : n \equiv 0 \pmod{2}이면,\ n = n \div 2$ $op_3 : n = n - 1$ 그리고 $n$을 1로 만들기 위해 사용하는 연산의 최소 횟수를 $f(n)$이라고 하자. $n$에 대하여 $op_1,\ op_2,\ op_3$을 모두 사용할 수 있을 때 $n$을 1로 만들기 위해 사용하는 연산의 최소 횟수를 각각 $f_1,\ f_2,\ f_3$라고 하자. 그렇다면 $n \equiv 0 \pmod{3}$이면 $op_1$을 사용하여 $n$을 $n \div 3$으로 줄일 수 있기 때문에 $f_1..

  Read More

• [Algo Rhythm🕺💃] BOJ 10971 - 외판원 순회 2

  Algo Rhythm🕺💃/BOJ 2021. 7. 10. 01:22

  💫문제 분석 도시들의 수를 $n$, 각 도시를 $C_i\ (1 \le i \le n)$, 그리고 $C_a$에서 $C_b$로 이동하는데 드는 비용을 $W_{a, b}$라고 하자. 이때 $W_{a, b} \ne W_{b, a}$일 수도 있고 $W_{a,b} = 0$ 이면 $C_a$에서 $C_b$로 이동할 수 없다. 우리는 외판원이 한 번 갔던 도시를 재방문하지 않을 때 어느 한 도시에서 출발해 $n$개의 도시를 모두 거쳐 다시 원래의 도시로 돌아올 때 드는 최소 비용을 구해야 한다. 이때 주의할 점이 외판원이 어느 도시에서 출발하는가는 중요하지 않다는 것이다. 왜냐하면 아래 그림과 같이 최소 비용으로 이동가능한 경로는 '원순열'의 형태를 띄기 때문이다. 따라서 이 문제는 최소 비용을 가진 원순열을 찾는 문제..

  Read More

• [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$을 ..

  Read More

• [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$개의 칸을 선택할 때 한 가지 조건은 이미 선택..

  Read More

• [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 ..

  Read More

• [Algo Rhythm🕺💃] BOJ 1748 - 수 이어쓰기 1

  Algo 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)$개이다..

  Read More