공작소

1116, 1117, 1118, 1119, 1120, 1121, 1122, 1123, 1124 정수, 실수 사칙연산 문제이다. 문제를 보고 식을 그대로 출력하면 풀이할 수 있다. 1125 %o, %X 를 이용해 풀이할 수 있다.

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

>> 문제 바로가기 (https://www.acmicpc.net/problem/20047) 문제 100 원짜리 동전과 10 원짜리 동전이 임의의 순서로 한 선 위에 나열되어 있다고 하자. 이제 여기서 ‘두 손가락 이동’ 을 아래와 같이 정의하자. 단계 1: 임의의 두 동전을 선택한다. 단계 2: 단계 1 에서 선택한 두 동전을 둘의 순서를 유지한 채 임의의 위치로 이동한다. (두 동전 모두 제자리에 있거나 두 동전의 순서를 유지한다면 하나만 이동해도 된다.) ‘두 손가락 이동’ 후에도 다른 동전들 간의 순서는 그대로 유지된다. 예를 들어 100 원을 o, 10 원을 x 라 했을 때, 초기에 동전이 oxoxoxxxoo 와 같이 나열되어 있다 하자. 이제 이들 중 굵게 표시된 두 동전을 선택하여 두 손가락 ..

문제 크기 N의 1차원 양의 정수 배열로 이루어진 자벌레가 있다. 자벌레는 곤충이기 때문에 머리, 가슴, 배로 부위를 구분할 수 있다. 각 부위는 배열상에서 연속하는 구간으로 나타낼 수 있으며 배열상에서 머리는 왼쪽에, 가슴은 가운데에, 배는 오른쪽에 존재한다. 각 부위의 크기는 배열상에서 해당하는 구간의 값의 합으로 정의된다. 무지는 이 자벌레가 가슴이 배보다 크고 배가 머리보다 크다는 사실은 알고 있지만 어느 지점에서 머리 가슴 또한 가슴 배가 구분되는지 알지 못한다. 무지를 도와 구분될 수 있는 경우의 수를 구해주자. 엄밀하게는 다음 조건에 맞는 X,Y 쌍의 개수를 구해주자. 배열에 i번째 원소의 값을 A_i라 할 때 입력 첫 줄에 정수 N이 주어진다. (3 ≤ N ≤ 1 000 000) 두 번째 ..

문제 N개의 영단어들이 주어졌을 때, 가장 비슷한 두 단어를 구해내는 프로그램을 작성하시오. 두 단어의 비슷한 정도는 두 단어의 접두사의 길이로 측정한다. 접두사란 두 단어의 앞부분에서 공통적으로 나타나는 부분문자열을 말한다. 즉, 두 단어의 앞에서부터 M개의 글자들이 같으면서 M이 최대인 경우를 구하는 것이다. "AHEHHEH", "AHAHEH"의 접두사는 "AH"가 되고, "AB", "CD"의 접두사는 ""(길이가 0)이 된다. 접두사의 길이가 최대인 경우가 여러 개일 때에는 입력되는 순서대로 제일 앞쪽에 있는 단어를 답으로 한다. 즉, 답으로 S라는 문자열과 T라는 문자열을 출력한다고 했을 때, 우선 S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력하고, 그런 경우도 여러 개 있을 때에는..

문제 상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다. 하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다. 이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자. 상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다. 입력 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다. 이후 M개의 줄에 a와 b 쌍들이 입력된다..

문제 K사의 물류창고를 운영하는 도커 씨는 오늘 발주를 처리하기 위해 N 개의 컨테이너들을 적재해야 한다. 도커씨는 이 일을 하나의 로봇을 이용해 처리하려 한다. 로봇은 컨테이너를 옮길 때마다 컨테이너의 무게만큼 비용을 발생시킨다. 컨테이너마다 우선순위가 있는데 우선순위는 1 이상 M 이하의 정수로 표현된다. 우선순위가 1에 가까울 수록 높은 우선순위를 가지고, M에 가까울 수록 낮은 우선순위를 가진다. M개의 각 우선순위에 대하여 해당 우선순위를 갖는 컨테이너가 적어도 하나 존재한다. 컨테이너는 레일을 통해 하나씩 오고, 우선순위가 낮은 컨테이너를 먼저 적재한다. 낮은 우선순위의 컨테이너들이 모두 적재되지 않은 상태에서 높은 우선순위의 컨테이너가 온다면 레일의 처음으로 보낸다. 레일의 처음으로 보낼 때..

문제 프로젝트 하느라 바쁜 득수는 밥 먹을 시간이 부족하다. 그래서 주로 찾는 식당 네 개 중 하나에서 하루에 한 번 밥을 먹는다. 귀찮으면 굶을 때도 있다. 늘 새로운 느낌을 받고 싶었던 득수는 다음과 같은 규칙으로 다음날 갈 식당을 정한다. 첫날에는 굶거나, 임의로 원하는 식당 하나를 골라서 간다. 어제 굶지 않았다면, 오늘은 식당을 가지 않아도 된다. 어제 식당을 가지 않았다면, 오늘은 식당을 가서 밥을 먹어야 한다. 오늘 간 식당은 다음날 가지 않는다. 오늘 간 식당과 이웃한 식당은 다음날 가지 않는다. 만약 2번 식당을 오늘 갔다면, 다음날 1, 2, 3번 식당은 가지 않는다. 따라서 새로운 느낌을 받으려면 4번 식당을 가거나 굶어야 한다. 득수가 N일 치 식단표를 만들려고 한다. 위 규칙을 따..

문제 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 N×M 크기의 직사각형 지도로 나타낼 수 있으며, 1×1크기의 정사각형으로 나누어져 있다. 구사과의 위치는 (i, j)로 나타낼 수 있으며, (i, j)는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸을 의미한다. 지도의 각 칸에는 E, S, B중의 한 문자가 쓰여져 있는데, 구사과는 이 문자를 이용해서 이동한다. 구사과의 위치가 (i, j)인 경우에 E가 쓰여져 있는 칸에 서 있었다면 (i, j+1)로, S의 경우에는 (i+1, j)로, B의 경우에는 (i, j+1) 또는 (i+1, j)로 순간이동한다. 구사과는 지치지 않기 때..

문제 N개의 정수로 이루어진 수열 a1, ... , aN이 있다. 택희는 해당 수열이 증가수열 혹은 감소수열이 되게 만들고 싶다. 증가수열은 모든 i(1 ≤ i arr[i]: up.append([]) up[-1].append(arr[i]) down = [[arr[0]]] for i in range(1, n): if arr[i-1] = up[0][0]: print(len(..