ALiNew ALiNew

BOJ

• [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 4375 - 1

  Algo 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..

  Read More

• [Algo Rhythm🕺💃]BOJ 2309 - 일곱 난쟁이

  Algo Rhythm🕺💃/BOJ 2021. 6. 22. 20:02

  문제 분석 문제에서 주어지는 아홉 난쟁이들의 키의 합은 일곱 난쟁이들의 키의 합인 100보다 크다. 따라서 이 문제는 $i$번째 난쟁이와 $j$번째 난쟁이 $(1 \le i, j \le n)$의 합이 초과값과 일치하는 $(i, j)$쌍을 찾는 문제로 이해할 수 있다. 문제 풀이 아홉 난쟁이의 키를 배열에 저장한 뒤, 이를 오름차순으로 정렬한다. 왜냐하면 일곱 난쟁이의 키를 출력할 때 오름차순으로 출력해야 하기 때문이다. 다음으로 이중 반복문을 통해 $(i, j)$쌍을 찾는다. 만약 찾았다면 $i$번째 난쟁이와 $j$번째 난쟁이를 제외한 모든 난쟁이들의 키를 차례대로 출력한 뒤 프로그램을 종료한다. 복잡도 분석 난쟁이 $n$명의 키가 입력으로 주어질 때, 시간 복잡도와 공간 복잡도는 다음과 같다. 시간 복..

  Read More

• [Algo Rhythm🕺💃]BOJ 14889 - 스타트와 링크

  Algo Rhythm🕺💃/BOJ 2021. 6. 18. 23:44

  문제 분석 스타트팀을 $T_{start}$, 링크팀을 $T_{link}$ 그리고 두 팀의 능력치를 각각 $S_{start}, S_{link}$라고 하자. 이때 각 팀에 속하는 사람들의 수는 두 팀 모두 축구를 하는 $N\ (4 \le N \le 20)$명의 절반인 $N / 2$ 명이다. 문제에서 요구하는 $min(|S_{start} - S_{link}|)$를 구하기 위한 가장 직관적인 방법은 $(T_{start}, T_{link})$의 모든 조합을 구한 뒤 각 조합의 $|S_{start} - S_{link}|$을 구하고 그 중 최소값을 찾는 것이다. 모든 조합을 구해야 하는 문제들은 주로 'backtracking'을 사용한다. 이 문제도 마찬가지로 backtracking을 사용하여 해결했다. 문제 풀이 ..

  Read More

• [Algo Rhythm🕺💃]BOJ 1620 - 정상 회담2

  Algo 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..

  Read More

• [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$ 이를 통해 우리가 최종적으로..

  Read More

• [Algo Rhythm🕺💃] BOJ 17528. Two Machines

  Algo Rhythm🕺💃/BOJ 2020. 8. 26. 21:06

  📚 문제 설명 스케줄링 최적화 회사인 SOPT 에 완료해야 할 n개의 작업 t1, t2, ..., tn 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각 작업 ti를 완료하기 위해 SOPT 는 머신 A 와 B 둘 중에 오직 하나를 선택할 수 있다. 작업 ti를 완료하기 위해 머신 A를 선택하면 ai시간이 걸리고 머신 B를 선택하면 bi 시간이 걸린다. 각 머신은 어느 순간에 최대 하나의 작업만 수행할 수 있으며, 한 작업이 시작되면 그 작업을 완료하기 전까지 다른 작업을 그 머신에서 수행할 수 없다. SOPT 는 모든 작업을 완료하기 위한 최소의 완료 시간을 구하고자 한다. 예를 들어, 세 개의 작업이 t1, t2, t3가 주어져 있고 a1 = 2, b1 = 3, a2 = 5, ..

  Read More