안주녕

미로탈출 로봇 대회를 개최하였다. 대회에 사용되는 미로는 가로(X), 세로(Y) 100이하의 크기이며, 미로를 한 칸 이동하는 데는 1초가 걸린다.       로봇이 출발점에서 도착점까지 가장 빨리 이동할 경우 걸리는 시간을 구하는 프로그램을 작성하시오. 입력 첫 줄에 미로의 크기 X, Y(1≤X, Y≤100)가 주어진다. 둘째 줄에 출발점 x, y 좌표와 도착점 x, y 좌표가 공백으로 구분하여 주어진다. 셋째 줄부터 미로의 정보가 길은 0, 벽은 1로 공백이 없이 들어온다. 주의 사항으로, 좌표는 좌측상단이 가장 작은 위치이며 이 위치의 좌표는 (1,1)이다. 출력 첫 줄에 출발점에서 도착점까지 가장 빠른 시간을 출력한다. 입력 예시 8 7 1 2 7 5 11111111 00000111 10110011 10111001 10111101 10000001 11111111 출력 예시 9 도움말   [ 입력 예시 2] 8 10  1 1 7 9  00000101 11001000 10000010 01101010 00000110 01010000 01110110 10000100 10011101 01000001   [ 출력 예시 2] 16   --------------------------------------------------------------------------------------------------- [ 입력 예시 3] 5 5 1 1 5 5 00000 01101 00100 01110 00000   [ 출력 예시 3] 8 #include <stdio.h> #define MAX 100000 int X, Y; int startX, startY; int target...

컴퓨터 실습실에는 총 M대의 컴퓨터가 일렬로 놓여있다. 이 컴퓨터는 왼쪽에 있는 것부터 순서대로 1~M의 번호가 매겨져 있다. 현재, 이 실습실에는 총 N명의 학생들이 이미 앉아있으며, 각각 들어온 순서에 따라 A1, A2, ..., AN번 컴퓨터 앞에 앉아있다. 곧 있으면 자습시간이 시작되기 때문에 총 M-N명의 학생이 더 와서 컴퓨터를 사용할 것이다. 각 학생들은 다른 학생이 자기 컴퓨터의 모니터를 보는 것을 싫어하므로 다음과 같은 방법으로 자리를 잡을 것이다. 1.      우선 학생이 없는 연속한 컴퓨터들의 그룹 중 가장 컴퓨터가 많은 그룹을 선택한다. 만약 이런 그룹이 여러 개라면 가장 왼쪽에 있는 그룹을 선택한다. 2.      그 다음, 선택한 그룹의 컴퓨터들 중 정 중앙에 있는 컴퓨터를 선택하여 자리를 잡는다. 만약 학생이 선택한 그룹의 컴퓨터가 짝수개인 경우 정 중앙 2개의 컴퓨터 중 왼쪽에 있는 컴퓨터에 자리를 잡는다. 정환이는 Q명의 친구들과 함께 팀 프로젝트를 해야 하기 때문에 Q명의 친구들이 어디에 앉을 지 알아야 한다. 다행히 정환이는 각 친구가 몇 번째로 실습실에 들어갔는지 알고 있다. 정환이를 도와 각 친구들의 위치를 구하시오. 입력 첫 번째 줄에는 컴퓨터의 수 M, 이미 자리를 잡은 학생의 수 N, 친구의 수 Q가 주어진다. 두 번째 줄에는 N개의 정수가 주어지는데, 이 값은 자리를 잡은 학생의 위치 Ai를 나타낸다. 이미 자리를 잡은 학생들은 앞서 말한 방법으로 자리를 잡지 않았을 수도 있음에 유의하여라. 세 번째 줄에는 Q개의 정수가 주어지는데, 이 값은 각 친구가 실습실에 들어간 순서 Bi를 의미한다. ( 이미 자리를 잡은 학생들 N명 중 정환이의 친구가 있을 수도 있다. ) 1 ≤ A1 < A2 < . . . < AN ≤ M, 1 ≤ B1 < B2 < . . . < BQ ≤ M....

사탕 공장에서는 요구에 따라 다양한 개수의 사탕을 담고 있는 포장을 하고 있다. 어느 날 갑자기 대형 이벤트가 생겨서 공장에 있는 모든 사탕들을 풀어서 하나로 포장 해야 한다.   A, B, C 3 개의 사탕 포장이 있을 때 이 포장들을 한번에 하나로 합칠 수는 없고, 한번에 2개씩만 합칠 수 있다. 예를 들면 A와 B를 먼저 합친 후 C를 다시 합치거나 A와 C를 먼저 합치고 B를 합치기, 혹은 B와 C를 먼저 합치고 A를 합칠 수 있다.   사탕 포장을 풀었다가 다시 합치는 순서는 매우 중요한데, 그 이유는 그 순서에 따라 전체 비용이 달라지기 때문이다.   사탕 포장 A와 B에 각각 a개와 b개의 사탕이 들어있다고 할 때 이 둘을 합치는 비용은 a + b라고 한다. 그러므로 A와 B를 먼저 합치고 C를 합치는 경우 그 전체 비용은 a + b + a + b + c이며, B와 C를 먼저 합치고 A를 합치는 비용은 b + c + b + c + a 이므로 그 둘은 서로 같지 않을 수 있다.   예를 들어, 각각 2, 2, 5개가 포장되어 있다면 A(2)와 B(2)를 합치는 비용은 4. 합쳐진 것(4)과 C(5)를 합치는 비용은 9로 총 13이 최소비용이다.   현재 공장에 포장되어 있는 포장 개수 N과 각각 포장에 들어있는 사탕의 개수 ni가 주어질 때, 이들을 하나로 합치는데 들어가는 비용의 최소(C)를 구하라. 입력 첫 번째 줄에는 포장 개수 N(1<=N<=5000)이 주어진다. 두 번째 줄에는 포장에 들어있는 사탕의 개수 ni(1<=ni<=100)가 주어진다. 출력 최소 비용을 출력한다. 입력 예시 3 2 2 5 출력 예시 13 #include <stdio.h> #define MAX 5003 int N; int ni[MAX]; int tree[MAX]...

농부 존은 소유하고 있는 소들의 사진을 찍기 위해 전문 사진 작가를 고용했다. 다양한 품종의 소를 소유하고 있는 존은 한 장의 사진에 모든 종의 소가 포함 되길 원한다. N 마리의 소가 모두 라인에 맞춰(즉, Y 좌표는 고정) 다양한 위치(즉, X 좌표로 값은 정수 값임)에 서 있다. 그리고 소들은 정수 값의 품종 아이디를 목에 걸고 있다. 존은 연속된 범위의 사진을 찍을 계획이다. 사진 비용은 크기에 비례한다. 즉, X 좌표의 범위가 작을수록 비용은 저렴해진다. 당신이 할 일은 존이 한 장의 사진에 모든 품종의 소들이 적어도 한 마리씩은 포함될 수 있게 하는 최소 비용을 계산하는 것이다. 입력 첫 번째 줄에 소들의 수 N이 입력된다. (1≤N≤50,000) 두 번째 줄부터 N개 줄에 걸쳐 소의 위치 (X 좌표)와 소의 품종 아이디(ID)가 공백으로 구분되어 입력된다. (1≤X, ID≤1,000,000,000) 출력 모든 품종이 포함되는 X 좌표의 최소 범위를 출력하라. 입력 예시 6 25 7 26 1 15 1 22 3 20 1 30 1 #include <cstdio> #include <map> #include <algorithm> #define MAXN 50000 using namespace std; map<int,int> C; pair<int,int> cows[MAXN]; int N,K; int photo(){ int i,j,k; int min_cost = cows[N-1].first-cows[0].first; i = 0, j = -1, k = 0; while(i < N && j < N){ while(k < K && ++j < N) k += !(C[cows[j].second]++); while(k >= K){ min_cost = min(min_cost,...

회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.       새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.   1.  원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.  2.  각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.   위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다.   회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최대값을 구하는 프로그램을 작성하시오. 입력 입력의 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번...

농부 희찬이의 N(1≤N≤80,000)마리의 소들은 "bad hair day"를 맞이하였다. 각 소들이 자신들의 촌스런 머리 모양을 부끄러워 하자, 희찬이는 소들이 다른 소들의 머리 모양을 얼마나 알 수 있는지를 알고자 했다. i 번째 소들은 키가 hi(1≤hi≤1,000,000,000) 이며, 동쪽(오른쪽)을 바라보고 서있다. 따라서, i번째 소는 자신의 앞 ( i+1, i+2,...)의 소들의 머리 모양만 볼 수 있으며, 앞에 자신의 키와 같거나 큰 소가 서 있을 경우 그 소의 앞에 있는 소들의 머리 모양을 볼 수 없다. 다음 예제를 고려해보자: ()의 숫자는 키를 나타낸다.  1 번 소는 2,3,4번소의 머리 모양을 볼 수 있다.  2 번 소는 어떤 소의 머리 모양도 볼 수 없다.  3 번 소는 4번 소의 머리 모양을 볼 수 있다.  4 번 소는 어떤 소의 머리 모양도 볼 수 없다.   5 번 소는 6번 소의 머리 모양을 볼 수 있다.  6 번 소는 모든 소들의 머리 모양을 볼 수 없다! i 번 소들이 볼 수 있는 머리 모양의 수를 Ci 이라고 할 때, C 1 부터 C N  까지의 합을 출력하는 프로그램을 작성하라. 위의 예제의 답은 3+0+1+0+1+0=5가 된다. 입력 입력은 두 줄로 이뤄지며 입력의 첫 번째 줄에는 N 이 입력된다.   그리고 그 다음 줄에는 N 개의 숫자가 주어지며, 해당 줄의 i번째 숫자는 hi를 뜻한다. 출력 C 1   부터 C N  까지의 합을 한 줄에 하나씩 출력한다. 입력 예시 6 5 2 4 2 6 1 출력 예시 5 #include <stdio.h> #define MAX 80000 int N; long long H[MAX]; long long stack[MAX]; int top = -1; long ...