윤만석

문제 n행 n열의 격자로 나뉜 운동장이 있다. 이 위에 k개의 돌멩이가 있는데, 하나의 돌멩이는 격자 한 칸에 정확히 들어가 있으며, 두 개 이상의 돌멩이가 한 칸에 들어가 있는 경우는 없다.사고의 위험을 없애기 위해 이 돌멩이를 모두 제거하고 깨끗한 운동장을 만들려고 한다. 돌멩이를 제거할 때에는, 한 행이나 한 열을 따라 직선으로 달려가면서 그 행이나 열에 놓인 돌멩이를 모두 줍는 방식을 쓴다.여러분이 할 일은 운동장의 상태가 주어졌을 때 최소 몇 번이나 달려가야 돌멩이 줍기를 끝낼 수 있는지 계산하는 것이다.입력첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째 숫자는 행 번호, 두 번째..

누구비트야? 그룹이름 ㅇ ㅣ ㅇ ㅇ ㅛ 문제리유나는 세일러복을 정말 좋아한다. 그래서 세일러복을 많이 많이 만들어서 다른 사람들에게도 입히려고 한다.세일러복을 만들기 위해서는 두 가지 재료가 필요하다. 바로 하얀 티셔츠와 세일러 카라이다. 둘을 사용해서 세일러복을 만드는 방법은 다음과 같다.그림 1: 세일러복의 제작 과정리유나는 세상 사람들의 하얀 티셔츠를 모두 세일러복으로 만들고 싶었지만, 예산과 시간 등의 부족으로 인해 N개의 하얀 티셔츠만을 구해올 수 있었다. 세일러 카라도 많이 만들어야 했지만, 마찬가지의 이유로 세일러 카라도 M개 밖에 만들지 못했다고 한다.게다가, 불행히도 세일러 카라를 너무 급하게 만들다 보니까 크기가 들쭉날쭉하게 되었다. 아무 티셔츠에나 아무 세일러 카라를 붙일 수 있는 것..

문제 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + 12 = 23 또는 1 + 10 = 11, 4 + 7 = 11, 11 + 12 = 23 수의 리스트가 주어졌을 때, 지민이가 모든 수를 다 짝지었을 때, 첫 번째 수와 어떤 수를 짝지었는지 오름차순으로 출력하는 프로그램을 작성하시오. 위의 예제에서 1 + 12 = 13으로 소수이다. 그러나, 남은 4개의 수를 합이 소수가 되게 짝지을 수 있는 방법이 없다. 따라서 위의 경우 정답은 4, 10이다. 입력 첫째 줄에 리스트의 크기 N이 주어진다. N은 50보다..

문제 그랜드마스터 승급까지 1승이 남은 욱제는 끔찍한 광경을 보고야 말았다. 팀원들이 게임을 던지기 시작한 것이다. 그렇게 승급을 포기하려던 찰나, 욱제는 적 팀도 던진다는 사실을 알아챘다! 이제 승부는 미궁 속으로 빠지게 되었다. 한 팀에는 N명의 플레이어가 있고, 각 팀원은 게임을 시작하기 전에 영웅을 한 명 선택한다. 이때 같은 팀에서 여러 명이 한 영웅을 선택할 수는 없다. 게임에는 수많은 영웅이 있고, 그 중 M개의 영웅은 게임의 승패를 결정지을 정도로 구린 영웅이다. 이런 영웅을 선택하는 것을 트롤픽이라고 불린다. (같은 게임이기 때문에 트롤픽의 수 M은 양 팀 모두 동일하다) 양 팀이 모두 게임을 던지자, 즐겜 분위기가 형성되었다. 각 팀원은 M개의 트롤픽 중 자신이 원하는 트롤픽들을 말하고..

문제 N(1 ≤ N ≤ 100)마리의 들쥐들과 M(1 ≤ M ≤ 100)개의 땅굴이 있다. 각각의 들쥐는 2차원 평면상의 한 위치에 있고, 각각의 땅굴들도 2차원 평면상의 한 점에 위치한다. 들쥐들을 잡아먹는 매가 들쥐들을 습격했을 때, 쥐들은 매를 피하기 위해서 땅굴 속으로 숨을 수 있다. 모든 쥐들이 땅굴에 숨을 수 있다면 매에 잡아먹히는 쥐가 한 마리도 없겠지만, 각각의 땅굴에는 한 마리의 쥐만 들어갈 수 있을뿐더러 매가 도착하는 시간과 쥐들이 땅굴로 도망치는 속도가 있기 때문에 항상 모든 쥐들이 도망갈 수 있는 것은 아니다. 매는 현재를 기준으로 S(1 ≤ S ≤ 100)초가 지난 후에 지상에 도착한다. 각각의 들쥐들은 매 초당 V(1 ≤ V ≤ 100)만큼의 거리를 움직인다(즉 V가 쥐들의 초속..

문제 세준이는 N개의 빈 칸이 있는 R×C크기의 체스판을 가지고 있다. 빈 칸에는 룩을 놓을 수 없지만, 공격을 할 수 있는지 없는지에는 영향을 미치지 않는다. 즉, 빈 칸을 사이에 두고도 공격을 할 수 있다. R×C크기의 체스판에 최대 몇 개의 룩을 서로 공격하지 않게 놓을 수 있는지 구하는 프로그램을 작성하시오. 룩은 자기와 같은 행 또는 열에 다른 룩이 있으면 잡을 수 있다. 입력 첫째 줄에 체스판의 크기 R과 C가 주어지고, 빈 칸의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 빈 칸의 좌표가 주어진다. 좌표는 (행, 열)의 형태로 주어지고, 가장 윗 행은 1번 행이고, 가장 왼쪽 열은 1번 열이다. R과 C는 300보다 작거나 같은 자연수이고, N은 600보다 작거나 같은 음이 아닌 정수이다...

문제 체스와 관련된 문제는 처음 알고리즘을 배우기 시작할 때 부터 접하게 된다. 가장 유명한 문제로는 N-Queen 문제가 있다. 이를 변형해서 N-Rook 문제를 만들 수 있다. Rook(룩) 은 체스에서 같은 행이나 같은 열의 아무 위치로 이동할 수 있는 체스 말이다. N × N 크기의 체스판에 룩을 최대한 많이 어떻게 배치할까? 라는 문제는 매우 쉽게 해결할 수 있다. 대각선으로 룩을 배치하면 된다. 문제를 좀 더 어렵게 만들어서, N x N 크기의 체스판에 폰이 몇 개 놓여있다. 이런 상황에서 룩을 최대 몇 개 배치할 수 있을까? 폰이 배치 되어 있으면, 룩은 폰에게 가로막혀 같은 열이나 같은 행의 모든 위치에 이동할 수 없다. 입력 첫 줄에 체스판의 크기 N이 주어진다. (1 ≤ N ≤ 100)..

문제 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 단, N명 중에서 K명은 일을 최대 2개할 수 있다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다. 출력 첫째 줄에 강..

문제 세준 주차장은 R×C크기의 직사각형 모양이다. 세준 주차장에는 N개의 차와, M개의 주차 구역이 있다. 그리고, 모든 차는 주차 구역에 주차하려고 한다. 교통 제한 때문에, 차는 주차장의 경계와 평행하게만 움직일 수 있고, 모든 차는 1초에 한 칸씩 움직일 수 있다. 보통 모든 차는 현재 위치에서 가장 가까운 위치에 있는 주차 구역에 주차를 하려고 한다. 하지만, 다음과 같이 생긴 주차장이라면 현재 위치에서 가장 가까운 위치에 주차하는 것이 비효율적이다. .C.....P.X... XX.......X..P XX.....C..... ‘C’는 차이고, 'P‘는 주차 구역, 'X'는 벽이고, '.'은 빈 공간이다. 만약 아래에 있는 차가 현재 위치에서 가장 가까운 곳에 주차를 한다면, 왼쪽 위에 있는 차는..

문제 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해서 축사를 운영했으나, 곧 문제가 발생하게 되었다. 바로 소가 자신이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다. 농부 존을 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1부터 M까지 매겨져 있다. 입력 첫째 줄에 소의 수 N과 축사의 수 M이 주어진다. (1 ≤ N, M ≤ 200) 둘째 줄부터 N개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 Si (0 ≤ Si ≤ M)이 먼저 주어지고..