STUDY

불! 문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간은 통과하지 못한다. 입력 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자들은 다음을 뜻..

중량제한 문제 N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다. 영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다. 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A..

피자 오븐 문제 피자를 굽는 전자식 오븐이 있다. 이 오븐에 재료는 넣고 정확히 $N$분 동안 동작을 시키고자 한다. 그런데 이 오븐에 준비된 버튼은 아래와 같은 동작을 하는 5가지이다. 즉, 각각의 버튼은 동작 시간을 추가시키거나 감소시킨다. 처음에 피자 오븐의 첫 시간은 0분으로 정해져 있다. 시간을 감소시키는 버튼을 눌러서 시간이 0분보다 작아지는 경우에는 0분으로 설정된다. $t$가 현재 오븐에 세팅된 시간, $t'$은 버튼을 누른 뒤의 시간을 의미할 때, 각 버튼은 다음과 같은 기능을 가지고 있다. ADDH: $t' = t + 60$ ADDT: $t' = t + 10$ MINT: $t' = t - 10$ ADDO: $t' = t + 1$ MINO: $t' = t - 1$ 예를 들어, 58분을 설..

화산쇄설류 문제 화산학자 윤재상은 어느 화산섬을 탐사하러 갔다가 곧 섬에 있는 화산들이 곧 폭발하기 시작할 것이라는 급보와 각 화산의 폭발 시점 정보를 받았다. 섬은 M행 N열의 행렬로 표현된다. 어떤 화산의 위치를 (x, y), 폭발을 시작한 시각을 t 라고 하자. t+δ 시각이 되면 δ ≥ |u-x|+|v-y|인 모든 (u, v)위치의 지대들은 높이 무관하게 화산쇄설류가 덮치게 된다. 재상인 빨리 탈출을 하고싶다. 재상이는 처음에 X행 Y열에 있다. 재상이는 단위 시간 당 상하좌우 한 칸만 움직일 수 있다. 재상이는 화산이 있는 위치와 화산쇄설류가 뒤덮인 곳은 갈 수 없다. 재상이는 화산쇄설류를 피해서 되도록 가장 높은 곳으로 피하고 싶고, 되도록 가장 빨리 도달하기를 원한다. 재상이가 화산쇄설류를 ..

아기돼지와 늑대 문제 산으로 둘러싸인 고리분지에 사는 아기돼지 삼형제는 엄마돼지로부터 독립하여 새 집을 지으려 합니다. 고리분지는 N × M 크기의 2차원 격자로 나타낼 수 있고 각 칸의 지형은 초원, 빙판, 산 중 하나입니다. 고리분지에는 돼지가족들 뿐만 아니라 늑대들도 살고 있습니다. 늑대는 상하좌우 인접한 칸 중 산이 아닌 칸으로 이동할 수 있습니다. 만약 이동한 칸이 빙판이라면 초원을 밟거나 산에 부딪칠 때까지 이동한 방향으로 미끄러집니다. 산에 부딪친 경우 늑대는 빙판 위에 가만히 서있을 수 있고 다시 다른 방향으로 이동할 수 있습니다. 게으른 아기돼지들은 지푸라기로 집을 지을 예정이기 때문에 늑대가 집이 있는 칸에 도착하기만 한다면 손쉽게 침입할 수 있습니다. 고리분지에 사는 늑대들이 도달할 ..

거짓말 문제 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다. 사람의 수 N이 주어진다. 그..

농장 관리 문제 농부 민식이가 관리하는 농장은 N×M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 경비원를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다. 산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다. 문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다. 입력 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는..

맹세 문제 위대한 화학자 김선영은 그를 바라보며 굳은 맹세를 했다. 난 오늘부터 원소 기호로 이루어진 단어만을 말할 것이다. 선영이는 "I Am CLaRa"를 말할 수 있다. I 는 아이오딘, Am은 아메리슘, C는 탄소, La는 란타넘, Ra는 라듐이다. 또, 선영이는 "InTeRnAtIONAl"도 말할 수 있다. 하지만, "collegiate", "programming", "contest"는 원소 기호로 이루어진 단어가 아니기 때문에 말할 수 없다. 단어가 주어졌을 때, 선영이가 말할 수 있는 단어 인지 (원소 기호가 연결된 단어) 아닌지를 구하는 프로그램을 작성하시오. (대소문자는 가리지 않는다) 다음은 이 문제에서 사용하는 원소 주기율표이다. H He Li Be B C N O F Ne Na Mg ..

레이저빔은 어디로 문제 레이저박스라는 게임은 정사각형 모양의 n x n 보드에서 진행한다. (체스판을 상상하면 된다) 레이저박스의 임의의 칸마다 우향우 거울이라는 장치가 설치되어 있고, 마지막으로 레이저 한개가 설치되어 있다. 레이저는 판의 끝에만 설치 될 수 있는데, 행의 맨 아래/맨 위, 열의 오른쪽 끝/왼쪽 끝에 설치 될 수 있다. 레이저에서 나온 빔은 그 행 혹은 열을 질러서 반대쪽을 비춘다. 게임은 우향우 거울을 임의의 칸마다 설치한 후, 레이저를 배치를 해 놓은 이후에 시작한다. 레이저를 켰을 때 나온 빔이 우향우 거울을 통과하면 진입한 방향과는 관계 없이 오른쪽으로 90도를 꺾어 다시 나아간다. 레이저 빔이 마지막으로 어느 좌표를 향해 비춰지는지 구하라. 입력 첫 줄에는 테스트케이스의 총 개..

경로 게임 문제 현정이는 경로 게임을 하고 있다. 경로 게임은 정사각형 칸으로 이루어져 있는 직사각형 격자판에서 진행된다. 격자판의 행의 개수는 항상 2이며, 열의 개수는 양수이다. 각 칸은 검정색 또는 하얀색으로 칠해져 있다. 격자에서 왼쪽-오른쪽 경로는 시작 칸이 가장 왼쪽 열에 있는 칸이고, 마지막 칸이 가장 오른쪽 열에 있는 경로이다. 이때, 경로 상의 모든 칸은 하얀색이어야 하며, 경로상에서 연속하는 칸은 모두 인접해야 한다. 격자판의 하얀색 칸을 검정색 칸으로 바꾼 경우에도 왼쪽-오른쪽 경로가 존재할 수도 있다. 이때, 왼쪽-오른족 경로가 존재하면서 바꿀 수 있는 하얀색 칸의 최댓값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 열의 개수 M이 주어진다. (M ≤ 50) 둘째 줄부터 두 개의..