백준 2025 중앙대학교 프로그래밍 경진대회

백준 33674번 하늘에서 떨어지는 N개의 별

• 각 점 i에서 청소 없이 f일간 별이 쌓이면 각 점의 누적 별은 f × s_i
• 폭발은 별의 개수가 K를 초과할 경우 발생하므로, 각 점에서 안정하게 유지하기 위해서는 f × s_i ≤ K 를 만족해야 함
• 따라서 각 점 i에 대해 f ≤ floor(K / s_i) 이어야 함
  • 모든 점에 대해 동시에 만족시키려면 `f ≤ min_{1≤ i ≤ N} floor(K / s_i)` 가 됨
  • 해당 값을 m이라고 정의했을 때, 한 청소 사이에 연속해서 최대 m일 동안 별 쌓기를 안전하게 할 수 있음

 

• D일을 m일 간격으로 나누면, 필요한 청소 횟수는 ceil(D / m) - 1
  • 초기 상태는 이미 0이므로 첫 구간은 청소할 필요 없음

 

 

백준 33675번 L-트로미노 타일링

• N이 홀수인 경우: 3 * N의 면적은 타일 하나당 3칸씩 채우므로 타일 수가 N가 되지만, 홀수 열에서는 L-트로미노 모양을 정확히 채울 수 없으므로 경우의 수는 0
• N이 짝수인 경우: 직사각형을 3 * 2 블록 (즉, 열 2개씩)으로 분할할 수 있으며, 각 3 * 2 블록을 채우는 방법은 2가지
  • 따라서 전체 3 * N 직사각형을 채우는 경우의 수는​ 2^(N/.2)

 

 

백준 33676번 우주 여행

• 이동시간=t(출발칸)−t(도착칸)이며, 음수가 될 경우 절댓값만큼 `시간을 거슬러` 가게 되므로 텔레코핑 효과에 의해 최종 이동시간의 총합은 t(1 , 1) − t(N, M)가 되어 경로에 상관없이 동일
  • 따라서 “이동 소요 시간의 총합이 최소인 경로”를 구하는 문제는 정확히 L번의 이동으로 (1,1)에서 (N, M)으로 갈 수 있는 경로 하나만 출력하면 되는 문제

 

• (1,1)에서 (N, M)까지 이동할 때 필요한 최소 횟수는 (N − 1) + (M − 1)
• 실제 경로의 이동수가 L번이어야 하므로 (L − 최소 횟수) 번의 여분의 이동이 필요한데 한 번의 `루프`는 두 번의 이동으로 이루어지므로 (L − 최소 횟수)는 반드시 짝수여야 함
  • 조건에 맞지 않으면 -1을 출력
  • 조건에 맞을 경우 (1, 1)에서 ((L - 최소 횟수) / 2) 번만큼 `RL` 추가하여 이동 횟수가 L번이 되도록 처리

 

 

백준 33677번 푸앙이와 콩나무

• 각 상태에 대해 `최소 일수`가 최우선이며, 같은 일수에 대해서만`“물 사용량의 총합`을 최소화하는 것이 목표
  • BFS를 통해 단계별로 탐색하되, 이미 같은 단계에 도달한 상태에 대해 더 적은 물을 사용한 경우 갱신하여 다시 그 상태에서의 전이를 고려하는 방향으로 구현

 

 

백준 33678번 로마의 휴일

• 문제의 핵심은 `휴가 (연속된 S일)를 최대한 길게` 계획하면서 수입이 K 이상이 되는 S의 최댓값을 찾는 것
• 휴가 기간을 늘리면 근무하는 날이 줄어 수입이 감소하므로 해당 문제는 `최대 휴가 가능 일수 S`를 이분 탐색으로 구현 가능

 

 

백준 33679번 세기의 대결

• 보스의 방어력이 처음에는 0이고, 총알을 사격할 때마다 그 위력으로 갱신되므로 안전하게 사격하기 위해서는 이전에 사격한 총알의 위력보다 큰 총알만 선택해야 함
  • 따라서 최적의 전략은 `최대 증가 부분 수열`을 구하는 것과 동일
  • N이 상대적으로 작기 때문에 O(N^2)으로 풀어도 무방함

 

 

백준 33680번  pn!$p^{n}!$과 쿼리

 

• `(p^n)! = p^k * N`의 형태로 나타낼 때, p와 서로소인 정수 N에 대해 p의 지수 k를 구하는 것
  • k = ∑ {i=1 ~ 무한대} floor(p^n / p^i)
  • 따라서 k = p^(n-1) + p^(n-2) + ... + p^0
  • 기하급수의 합 공식에 따라 k = (p^n - 1) / (p - 1)

 

 

백준 33681번 택배 상하차는 어려워

• 총 N 개의 도시와 (N - 1) 개의 도로가 있으므로 트리 구조
• 모든 택배는 처음 도시 1에 놓여 있으며, 도시 1에 있는 택배 중 목적지가 1인 것은 이미 배송된 상태
• 트럭은 LIFO 방식으로 택배를 하차하므로, 트럭 하나의 경로는 한 방향으로만 연속 전달 가능
  • 여러 분기로 갈라지는 경우, 한 노드에서 하나의 자식 방향으로는 기존의 트럭 경로를 유지할 수 있으나, 다른 자식 방향으로 배송하기 위해서는 해당 노드에서 새로운 트럭을 이용
  • 새로운 트럭에 옮길 때는 해당 분기에 속한 모든 택배가 추가적으로 1회의 상차와 1회의 하차 작업을 수행해야 하므로, 패키지 하나당 추가 작업 2회가 필요

 

• 트리 구조에서 각 도시를 루트부터 내려가는 DFS를 진행할 때, 각 노드 u에 대해 해당 노드와 그 아래 서브트리에 있는 패키지 총개수를 `P(u) = a[u] + ∑v∈자식(u)P(v)` 로 정의
  
  • 목적지가 1인 택배들은 이미 배송된 상태이므로 a[1] = 0

 

• 이후, 각 노드 u에서 자식 노드들 v들에 대해 트럭 경로를 하나만 유지할 수 있으므로
  • u에서 자식 노드들의 패키지 합계 childTotal=∑v∈자식(u)P(v)
  • 이 중 하나의 자식에 대해 기존 트럭 경로를 사용할 수 있으므로, 추가 비용이 없는 최댓값은 v가 u의 자식이라고 정의했을 때 max(P(v))
  • u에서 발생하는 추가 전송 비용은 childTotal - max(P(v)) 가 되고, 각 패키지는 2회의 추가 작업(상차+하차)을 수행하므로 최종 비용에 2배

 

• 최종적으로 모든 패키지에 대한 총비용은 (모든 패키지 상하차 작업) + 2 * (모든 배송에서 발생한 추가 비용)

 

 

백준 33683번 CPC 문제 정렬 순서

• 현재 배정할 난이도 후보를 나타내는 변수 currentDifficulty를 두고, 문제들의 허용 구간 [l, r] 조건을 만족하면서 하나씩 순차적으로 할당
• 문제들을 최소 허용값 l을 기준으로 오름차순 정렬한 뒤 현재 난이도 currentDifficulty를 적용할 수 있는 문제들을 최소 힙에 넣음
  • 이때 힙은 각 문제의 상한 값 r 기준으로 정렬되므로, 허용 범위가 가장 좁은 문제부터 처리 가능

 

• 우선순위 큐에서 상한 r 값이 가장 낮은 문제를 선택한 후, 현재 난이도 currentDifficulty를 해당 문제의 섹션에 할당할 수 있는지 판단
• 만약 해당 문제의 상한 값 r이 currentDifficulty 이상이면
  • 문제에 currentDifficulty를 할당하고,
  • 난이도 후보인 currentDifficulty를 1 증가시켜 다음 할당에 사용하며 (새 섹션 생성),
  • 섹션 번호 또한 증가시킴

 

• 만약 문제의 상한값 r이 currentDifficulty보다 작지만, r + 1이 currentDifficulty와 같다면
  • 현재 난이도는 증가시키지 않고, 이전 난이도 (currentDifficulty - 1)를 할당
  • 이 경우, extra 문제를 사용하는데, extraProblems는 전체 문제 수에서 반드시 한 문제씩 배정해야 하는 섹션 할당 후 남는 문제 수(n – m)를 의미

 

• 만약 r + 1 < currentDifficulty인 경우에는, 해당 문제의 허용 범위 내에서 currentDifficulty 또는 그 이전 값을 할당할 수 없으므로 문제 할당이 불가능하다고 판단하고 종료시킴

 

 

개발환경:Visual Studio 2022

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~