낢이 사는 이야기

캐슬 디펜스 문제 캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다. 성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다..

차트 문제 민식이는 학교에서 다른 반 친구들이 개를 몇 마리 키우는지 궁금했다. 그래서, 세준이는 다른 반 친구들이 키우는 개의 수를 조사했다. 세준이네 학교에 개를 키우는 사람의 수는 총 100명이었다. 어떤 반에 개를 키우는 사람이 15명이면, 이 것은 15%와 같다. 민식이는 자기가 조사한 개의 수를 가지고 원형 차트를 만들었다. 10, 40, 10, 40 일때의 차트 모양은 다음과 같다. 또, 10, 40, 50 일때의 차트 모양은 다음과 같다. 민식이가 조사한 데이터를 이용해서 차트를 만들 수 있는 방법은 여러 가지가 존재한다. 민식이는 그 중에, 원의 중심을 지나는 선의 개수를 최대로 하고 싶어한다. (원의 중심을 지나는 선이란, 원을 이등분하는 선) 민식이 학교의 반의 개수와, 각 반에서 개..

킥다운 문제 세계적으로 유명한 엄지민 자동차 회사는 효율적인 킥다운 장치를 만들어달라는 의뢰를 받았다. 킥다운이란 자동차에서 낮은 기어로 바꾸는 장치를 의미한다. 연구 끝에 효율적인 킥다운 장치는 '이'와 '홈'이 불규칙하게 배열되어 있는 기어로 만들어져야 한다는 것을 알았다. 첫 번째 그림과 같이 두 기어 파트가 서로 마주보고 있게 된다. 튀어나온 것이 기어의 이, 들어간 곳이 홈이다. 그리고 이들을 두 번째 그림과 같이 서로 맞물리게 끼우는 것으로 킥다운 장치를 만들 수 있다. 하지만 문제는 맞물리게 하였을 때 가로 너비가 짧을수록 효율적인 킥다운 장치가 된다. 때문에 문제는 두 기어가 주어졌을 때 맞물리게 하는 가장 짧은 가로 너비를 구하는 것이다. 입력 첫 줄에는 첫 번째 기어 파트를 나타내는 1..

체커 문제 N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 움직이는 것이다. 입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 체커의 x좌표와 y좌표가 주어진다. 이 값은 1,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 수 N개를 출력한다. k번째 수는 적어도 k개의 체커가 같은 칸에 모이도록 체커를 이동해야 하는 최소 횟수이다. 예제 입력 4 15 14 15 16 14 15 16 15 예제 출력 0 2 3 4 풀이 체커를 최소로 이동시켜 k개의 체커가 같은 칸에 모이도록하는 좌표..

카드 섞기 문제 마술사 영재는 카드 더미를 이용한 마술을 개발하였다. 카드들에는 1부터 N까지의 숫자가 적혀있으며 초기 상태에는 1이 맨 위에 있으며 N개의 카드가 번호 순서대로 쌓여있다. 영재는 마술을 위해 (2, K) - 섞기를 만들었다. (2, K) - 섞기는 총 K + 1개의 단계로 이루어져있다. 첫 번째 단계는 카드 더미 중 밑에서 2K개의 카드를 더미의 맨 위로 올린다. 이후 i(2 ≤ i ≤ K + 1)번째 단계는 직전에 맨 위로 올린 카드 중 밑에서 2K - i + 1개의 카드를 더미의 맨 위로 올린다. 예를 들어, 카드의 개수가 5개 일 때 초기 상태에서 (2, 2) - 섞기를 하는 과정은 다음과 같다.(괄호 내에서 왼쪽에 있을수록 위에 있는 카드이다.) (1, 2, 3, 4, 5) → ..