백준
-
[Algo Rhythm🕺💃] BOJ 16926 - 배열 돌리기 1Algo 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회 회전하는..
-
[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)$..
-
[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..
-
[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 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 20170 - Commemorative DiceAlgo Rhythm🕺💃/BOJ 2021. 6. 21. 03:26
문제 분석 주사위 게임을 하는 첫번째, 두번째 플레이어를 각각 A, B라고 하고 A와 B의 주사위 중 임의의 한 면에 적힌 숫자를 각각 $\alpha, \beta$라고 하자. 이때 주사위는 6면이기 때문에 A와 B가 주사위를 던져서 나올 수 있는 경우의 수는 $6 \times 6 = 36$이다. 그리고 A가 B를 이기는 경우의 수인 $N_{win}$은 $\alpha \gt \beta$를 만족하는 모든 $\alpha$의 수와 같다. 따라서, A가 B를 이길 확률은 $N_{win} \over 36$이다. 이때, 문제에서 요구하는 것은 '더이상 나눌 수 없는' 분수 형태로 출력하는 것이기 때문에 분자와 분모를 최대 공약수로 나눠서 출력해야 한다. 문제 풀이 A와 B의 주사위 정보를 각각 배열에 저장한 뒤, $..
-
[Algo Rhythm🕺💃]BOJ 1620 - 정상 회담2Algo Rhythm🕺💃/BOJ 2021. 3. 12. 15:05
문제 분석 문제를 분석하는 효과적인 방법들 중 하나는 그림으로 표현해보는 것이다. 이 문제에서 N = 0, 2, 4, 6 일때 완벽하게 악수하는 경우들과 그 수를 그림으로 표현하면 아래와 같다. (이때 각 국가의 대표는 노드로 표현했다.) 그림에서 검은색 노드와 흰색 노드가 연결된 선분을 기준으로 왼쪽 영역을 $l$, 오른쪽 영역을 $r$라고 하자. 그리고 $a$개의 노드들이 완벽하게 악수할 수 있는 경우의 수를 $f(a)$라고 하자. 그렇다면 N =0, 2, 4, 6일때 완벽하게 악수할 수 있는 경우의 수는 아래와 같은 규칙이 있음을 알 수 있다. 이 규칙을 점화식으로 표현하면 다음과 같다. $f(N)= \begin{cases} 1, & if\ n = 0\\ \sum_{i=0}^{N-2} f(i) \t..
-
[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$ 이를 통해 우리가 최종적으로..