ALiNew ALiNew

Algo Rhythm🕺💃/BOJ

• [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 14501 - 퇴사

  Algo Rhythm🕺💃/BOJ 2021. 3. 11. 00:41

  문제분석 백준이는 $i (1 \le i \le N)$번째 날의 일을 하느냐 마느냐에 따라 얻을 수 있는 이익이 다르다. 단순히 생각하면 i번째 날의 일을 하는 경우와 안 하는 경우로 나눠서 모든 경우를 살핀 뒤 그 중 최대의 이익을 구하면 될 것 같다. 사실 그래도 된다. 하지만 조금 더 생각해보면 보다 더 효율적인 방법이 있다는 것을 알 수 있다. 앞서 말했듯이 백준이는 i번째 날의 일을 하느냐 마느냐에 따라 얻을 수 있는 이익이 다르다. 자세히 말하면 만약 i번째 날의 일을 한다면 $i + T[i]$번째 날의 일부터 하느냐 마느냐를 선택할 수 있고 만약 i번째 날의 일을 하지 않는다면 $i + 1$번째 날의 일부터 하느냐 마느냐를 선택할 수 있다. 즉, 백준이가 i번째 날의 일을 하느냐 마느냐를 결정..

  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 16288. Passport Control

  Algo Rhythm🕺💃/BOJ 2020. 9. 3. 10:32

  📚 문제 설명 $N$명의 입국 승객이 여권 심사를 위하여 그림 G.1 과 같이 입국 대기 줄에서 $[1, 2, … , N − 1, N]$ 순서로 기다리고 있다. 입국 승객은 준비된 $k$개의 여권 심사 창구 중 하나를 통과한 뒤 공항을 빠져나갈 수 있다. 입국할 때의 줄 선 승객의 순서를 $[1, 2, … , N − 1, N]$이라고 할 때 $k$개의 여권 심사 창구를 통과하여 입국장을 빠져나가는 순서 $[π_{1}, π_{2}, … π_{N−1}, π_{N}]$는 처음과 달라질 수 있다. $k$개 여권 심사 창구가 준비되어 있을 때, 이 입국장을 빠져나가는 순서가 가능한 순서인가를 계산해야 한다. 예를 들어 설명해보자. 만일 $N = 3, k = 2$ 라고 할 때 입국장을 빠져나가는 순서 중 $[1, ..

  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

• [Algo Rhythm🕺💃] BOJ 17626. Four Squares

  Algo Rhythm🕺💃/BOJ 2020. 8. 24. 15:06

  📚 문제 설명 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125^2 + 6^2 + 1^2 + 1^2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105^2 + 15^2 + 8^2 + 5^2. 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램..

  Read More

• [Algo Rhythm🕺💃] BOJ 17521. Byte coin

  Algo Rhythm🕺💃/BOJ 2020. 8. 24. 13:48

  📚 문제 설명 국제자본부동산회사(ICPC)는 바이트 코인(Byte Coin)에 자금을 투자하고 있다. 바이트 코인은 김박사가 만든 가상 화폐이다. 실제로는 바이트 코인 가격을 예상할 수 없지만 이 문제에서는 바이트 코인 가격 등락을 미리 정확히 예측할 수 있다고 가정하자. 우리는 1일부터 n일까지 n일 동안 그림 1과 같이 바이트 코인의 등락을 미리 알 수 있으며 우리에게는 초기 현금 W가 주어져 있다. 그림 1의 빨간색 네모는 해당 일자의 바이트 코인 가격을 나타낸다. 매일 바이트 코인을 매수하거나 매도할 수 있다고 하자. 다만 바이트 코인 하나를 나누어 매도하거나 매수할 수는 없다. 우리는 n일 날 보유하고 있는 모든 코인을 매도할 때 가지고 있는 현금을 최대화하고 싶다. 그림 1. 10 일간 바이트..

  Read More

• [Algo Rhythm🕺💃] BOJ 17520. Balanced String

  Algo Rhythm🕺💃/BOJ 2020. 8. 24. 13:36

  📚 문제 설명 0과 1로 이루어진 이진 문자열 0101101은 0과 1의 개수의 차이가 1 이하이다. 뿐만 아니라, 첫 번째 문자를 포함하는 모든 부분 문자열 0, 01, 010, 0101, 01011, 010110, 0101101 모두 0과 1의 개수의 차이가 1 이하이다. 이와 같이, 이진 문자열 중에서 첫 번째 문자를 포함하는 모든 부분 문자열의 0과 1의 개수의 차이가 1이하인 문자열을 균형잡힌 문자열이라 부른다. 문자열 자체도 자신의 부분 문자열이다. 양의 정수 n 이 주어질 때, 길이가 n 인 이진 문자열 중에서 균형잡힌 문자열의 수를 구하는 프로그램을 작성하시오. 예를 들어, n = 3인 경우에는 010, 011, 100, 101 네 개의 문자열이 균형잡힌 문자열이다. 입력 입력은 표준입력을..

  Read More