STUDY

계산 로봇 문제 M개의 행(가로줄)과 N개의 열(세로줄)이 있는 격자의 각 칸에는 로봇이 있다. 각 행에는 위에서부터 아래로 1부터 M까지의 번호가 붙어 있고, 각 열에는 왼쪽에서부터 오른쪽으로 1 부터 N까지의 번호가 붙어 있다. 이를 통해 격자 칸의 위치를 (행 번호, 열 번호)의 좌표로 표시할 수 있다. 각 로봇은 하나 이상의 입력 값, 하나의 저장 값, 하나의 출력 값을 가진다. 로봇들은 제일 왼쪽 열의 로봇들부터 열 번호 순서대로 동작한다. 같은 열에 있는 로봇들은 동시에 동작 한다. 로봇들의 동작은 다음과 같다. (표현 |A|는 정수 A의 절댓값을 의미한다. 즉, A ≥ 0인 경우 |A| = A, A < 0 인 경우 |A| = −A.) 제일 왼쪽 열에 있는 로봇의 입력 값은 0 하나로 정한다 ..

패셔니스타 https://www.acmicpc.net/problem/5535 문제 상근이는 학교에 관심있는 사람이 생겼기 때문에, D일동안(1일~D일) 입을 옷을 계획하기로 했다. 옷의 스타일과 최고 기온은 매우 밀접한 관계가 있기 때문에, 상근이는 D일 동안 일기 예보를 바탕으로 계획을 세우려고 한다. i일의 최고 기온은 Ti이다. 상근이는 총 N가지 옷을 가지고 있고, 이 옷은 모두 1번에서 N까지 번호가 붙여져 있다. 옷 j(1 ≤ j ≤ N)는 최고 기온이 Aj 이상 Bj 이하인 날에만 입을 수 있다. 또, 각 옷의 화려한 정도는 Cj이다. 상근이는 일기예보를 참고해 어느 날 어떤 옷을 입을지 결정하려고 한다. 같은 옷을 여러 번 입어도 되고, 한 번도 입지 않은 옷이 있어도 상관 없다. 비슷한 ..

마리오 파티 문제 일렬로 된 보드가 있다. 맨 왼쪽은 시작점이고, 맨 오른쪽에는 별이 있다. 매 턴마다 플레이어는 1부터 S까지의 자연수가 균일한 확률로 나오는 주사위를 굴린 뒤 나온 수만큼 앞으로 이동한다. 플레이어가 멈춘 칸에는 숫자가 쓰여 있는데, 거기에 쓰인 만큼 (양수일 때) 코인을 얻거나 (음수일 때) 잃는다. T턴이 지나면 게임이 종료된다. 예를 들어 보드가 위와 같고, S=4, T=5라고 하자. 주사위를 굴려서 2, 3, 4, 1, 1이 나오면 총 수익은 170코인이 된다. 반면 주사위를 굴려서 1, 3, 2, 4, 1이 나오면 총 수익은 220코인이 된다. 꼭 별이 있는 칸에 정확히 멈출 필요는 없다. 별이 있는 칸을 지나가면 별을 얻을 수 있기 때문이다. 보드가 안 좋아서 총 수익이 음..

달려달려 문제 어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정확히 N분에 완주할 수 있는 시간 안배능력까지 갖추게 되었다. 그래서 N분동안 학생들은 달릴지 아님 쉴지 결정하여야 한다. 그러나 학생들도 인간이기 때문에 계속 달릴 수는 없다. “지침 지수”라는 것이 있어서 1분을 달린다면 “지침 지수”는 1이 올라간다. 반대로 1분을 쉰다면 “지침 지수”는 1이 내려간다. 또한 이 “지침 지수”가 M보다 커지면 학생들은 더 이상 달릴 수가 없다. 아주 특이하게도 학생들은 시간에 따라 달릴 수 있는 거리가 다르다. 만약 I분에 달렸다면 Di 만큼의 거리를 달릴 수 있다. (..

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

자두나무 문제 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다. 매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만..

토끼가 정보섬에 올라온 이유 문제 토끼가 정보섬에 올라왔다! 정보섬은 N행 M열의 격자로 나타낼 수 있으며, 어째서인지 여기저기에 당근이 떨어져 있다. 방금 토끼 한 마리가 정보섬 정문으로 들어왔다. 토끼의 왼쪽에선 사나운 늑대가 쫓아오고 있어서, 토끼는 →, ↘, ↗ 방향으로만 이동한다. 토끼는 나가는 길에 최대한 많은 당근을 줍고싶다. 정문은 늑대 때문에 위험하므로 쪽문으로 나가야 하며, 토끼가 당근을 줍기 위해서는 그 당근이 있는 위치를 지나야 한다. 토끼가 어떤 쪽문에 도착했을때 반드시 그 문으로 탈출할 필요는 없으며, 더 움직여서 다른 쪽문으로 탈출해도 된다. 토끼는 얼마나 많은 당근을 주워갈 수 있을까? 토끼의 이동을 명확하게 정의하면 다음과 같다. 격자의 r행 c열 위치를 (r, c)라고 하..

1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다. 숫자가 ..

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

RGB거리 2 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠..