[Baekjoon] 1006 – 습격자 초라기
📖 문제 이해하기 이 문제는 도넛 모양의 건물에 배치된 적들을 효율적으로 제압하기 위한 최소 특수소대 개수를 구하는 문제입니다. 건물은 내부 원과 외부 원으로 이루어진 이중 원형 구조이며, 각 원은 N개의 구역으로 나뉘어 총 2N개의 구역이 존재합니다. 특수소대는 W명으로 구성되며, 한 구역만 점령하거나 인접한 두 구역을 함께 점령할 수 있습니다. 여기서 인접이란 같은 경계를 공유하는 구역을…
[Baekjoon] 12920 – 평범한 배낭2
📖 문제 이해하기 이 문제는 고전적인 배낭(Knapsack) 문제의 변형입니다. 민호는 캠프에 가기 위해 가방을 싸려고 하는데, 각 물건은 무게와 만족도를 가지고 있습니다. 일반적인 배낭 문제와 다른 점은, 같은 물건을 여러 개 넣을 수 있다는 것입니다. 단, 각 물건은 최대 K개까지만 존재합니다. 예를 들어, 무게 3kg, 만족도 4인 물건이 5개 있고, 가방의 최대 무게가 10kg이라면, 우리는…
2338. Count the Number of Ideal Arrays
https://leetcode.com/problems/count-the-number-of-ideal-arrays/description 📖 문제 해석 길이가 n인 0‑인덱스 배열 arr가 “이상적(ideal)”이려면 두 가지 조건을 만족해야 합니다. 우리가 구해야 하는 것은 가능한 서로 다른 이상적 배열의 개수이며, 결과는 1_000_000_007으로 나눈 나머지입니다. 간단한 예로 n = 3, maxValue = 4를 생각해 보면, 제약을 보면 n과 maxValue 모두 최대 10<sup>4</sup>로, 단순 완전탐색은 불가능합니다. 🧠 첫 시도와 그 한계 가장…
[Baekjoon] 2568 – 전깃줄 2
https://www.acmicpc.net/problem/2568 전깃줄이 서로 엉켜있는 모습을 상상해보세요. 두 전봇대 사이에 여러 개의 전깃줄이 연결되어 있는데, 일부는 서로 교차하여 합선의 위험을 만들고 있습니다. 이 문제는 교차하는 전깃줄들 중 최소한의 개수만 제거하여 나머지 전깃줄들이 모두 평행하게 만드는 것이 목표입니다. 문제를 좀 더 구체적으로 살펴보면, 각 전깃줄은 A 전봇대의 특정 위치와 B 전봇대의 특정 위치를 연결합니다. 예를 들어 A의…
Finding the Longest Palindromic Path in a Graph
Link: https://leetcode.com/problems/longest-palindromic-path-in-graph/ 📖 Interpreting the Problem We’re given an undirected graph with n nodes, each labeled with a character. Our goal is to find the maximum possible length of a palindrome that can be formed by visiting a sequence of unique nodes along a valid path. Importantly, we may start at any node and travel…
Coloring a Grid with No Two Adjacent Cells the Same
Link: https://leetcode.com/problems/painting-a-grid-with-three-different-colors/ 📖 Interpreting the Problem Imagine you’re handed an empty grid of size m x n, and you need to fill every single cell using one of three colors: red, green, or blue. However, there’s a twist: no two adjacent cells—either vertically or horizontally—can share the same color. Let’s break it down with a…