문제 링크https://www.acmicpc.net/problem/32188 문제포탈 게임은 직선 위에서 진행되는 게임이다. 직선에는 0부터 N − 1까지의 번호가 매겨진 N개의 칸이 존재한다. 게임의 목표는 0번 칸에서 출발해 N − 1번 칸에 가능한 한 빠르게 도착하는 것이다.이 게임에는 포탈이 총 C개 존재하며, 포탈은 레드 포탈과 블루 포탈로 총 두 종류가 있다. 각 칸에는 포탈의 시작 지점이 최대 1개 존재할 수 있다. 시작 지점이 ai번 칸에 있는 포탈을 이용하면, 해당 포탈의 끝 지점인 bi번 칸으로 이동하게 된다. 포탈은 시작 지점에서 끝 지점으로만 이동할 수 있기 때문에 동일한 포탈을 이용해 bi번 칸에서 ai번 칸으로는 이동할 수 없다.포탈 게임에서는 N − 1번 칸에 도착하기 전까지 ..

문제 링크https://www.acmicpc.net/problem/32177 문제2차원 평면상에 살고 있는 푸앙이는 신입생으로 대학에 입학하게 되었다. 대학에 입학한 푸앙이는 활발한 성격으로 N명의 친구들을 사귀었고, 친구들을 1번, 2번, ⋯, N번으로 부르려고 한다.푸앙이는 그중 몇몇 친구들과 함께 사진을 찍게 되었다. 친구들에게 찍은 사진을 받고 싶지만 움직이기 귀찮은 푸앙이는 이 사진들을 가만히 앉아서 에어드롭으로 받으려고 한다.에어드롭은 보내는 휴대폰과 받는 휴대폰 사이의 버전 차이가 T 이하이면서 유클리드 거리로 최대 K만큼 떨어진 거리의 기기에만 사진을 전송할 수 있으며, 푸앙이와 사진을 가지고 있었던 친구의 휴대폰 버전 차이가 T보다 크더라도 다른 친구들을 이용한 간접적인 경로가 있다면 사..

문제 링크https://www.acmicpc.net/problem/14622 문제인하대학교에 다니는 대웅이는 정수론을 정말 좋아한다. 정수론을 광적으로 좋아하는 대웅이는 어느 순간부터 소수를 외우기 시작했고 어떤 수를 말하면 그 수가 소수인지 아닌지 판별할 수 있는 능력을 가지게 되었다. 인하대학교에 소수의 신이 있다는 소문이 퍼지자 인상대학교의 소수 마스터 규성이는 대웅이에게 도전장을 내밀었다.둘은 누가 더 소수를 사랑하는지 내기를 하기로 하였다.하지만 누가 더 소수를 사랑하는지에 대한 기준이 없으므로 소수 게임을 이용하기로 하였다.소수게임의 규칙은 다음과 같다.  두 사람이 번갈아가며 소수를 말한다.소수가 아닌 수를 부르게 될 경우 상대방은 지금까지 상대방이 말한 소수중에서 3번째로 큰 수만큼 점수를..

문제 링크https://www.acmicpc.net/problem/32339 문제세종이는 조선 시대의 지도인 대동여지도를 보면서 한양을 포함한 모든 지역을 연결하는 도로를 설치한다면 비용이 얼마나 들지 궁금해졌다.설치할 수 있는 도로의 종류는 총 3가지로 도보 전용 도로, 말 전용 도로, 마차 전용 도로가 있다.세종이는 지역을 연결할 수 있는 모든 도로를 전부 설치하고 싶지만 국고가 부족한 관계로 최소한의 비용을 사용하여 모든 지역을 이동할 수 있도록 도로를 설치하려 한다. 만약 최소한의 비용으로 도로를 설치할 수 있는 경우가 여러가지라면, 조정에서 지정해준 우선순위가 1번째인 도로가 가장 많은 순으로, 이 경우도 여러가지라면 우선순위가 2번째인 도로가 가장 많은 순으로 설치하려 한다.세종이를 도와 최소..

문제 링크https://www.acmicpc.net/problem/32770 문제세종이는 오늘따라 집이 너무 가고 싶어서 외출을 하기로 했다. 학교와 집을 왕복할 때는 버스를 이용하는데, 귀교 시간에 맞춰 돌아오기 위해서는 학교에서 집으로 갔다가, 학교로 다시 돌아오는 데 걸리는 시간을 알아야 한다.세종에는 E개의 버스 노선이 있다. 각 노선의 버스는 정해진 출발 정류장에서 도착 정류장으로만 이동하며, 반대 방향으로는 이동하지 않는다. 단, 세종이는 정말 운이 좋아서 정류장에 도착하면 언제나 바로 원하는 버스에 탈 수 있다. (와! 정말 부럽다)최대한 오래 집에 있고 싶어 하는 세종이를 위해 학교에서 집으로 다시 집에서 학교로 돌아오는데 걸리는 최소 시간을 구해주자. 입력첫째 줄에 버스 노선의 수 E가 ..

문제 링크https://www.acmicpc.net/problem/30024 문제옥수수밭 주인 민석이는 한 해 동안 열심히 기른 옥수수를 수확하려고 한다. 옥수수밭은 N행 M열의 격자로 생각할 수 있는데, 격자의 각 칸에는 한 그루의 옥수수가 심어져 있다. 민석이는 각 옥수수의 가치를 측정해서 서로 다른 정수 1, 2, ⋯, N × M을 부여했다.  민석이는 처음에 옥수수밭 바깥에 위치한다. 민석이는 옥수수밭 바깥을 돌아다니면서 옥수수밭 바깥과 인접한 칸의 옥수수를 수확할 수 있다. 또는 옥수수밭 안에서 옥수수를 수확한 칸으로만 돌아다니면서 현재 위치한 칸에서 상하좌우로 인접한 칸의 옥수수를 수확할 수 있다.그런데, 민석이는 옥수수의 생산량 조절을 위해서 K그루의 옥수수만 수확하려고 한다. 민석이는 현재..

문제 링크https://www.acmicpc.net/problem/1941 문제총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.강한 결속력을 위해, 7명의 자리는..

문제 링크https://www.acmicpc.net/problem/26607 문제블루아카이브에 있는 아비도스 고등학교 학생, 스나오오카미 시로코는 은행 터는 것을 자주 시뮬레이션한다.  어느 날, 정말로 은행을 털어보고 싶다는 생각이 든 시로코는 은행을 털 준비를 하기 시작했다. 우선, 은행 터는 것을 함께 할 팀을 만들 것인데, 경쟁을 뚫고 마지막까지 살아남은 n명 중에서 최종적으로 k명을 팀원으로 선발할 계획이다. 지원자들은 각각 힘과 스피드 수치 a, b가 주어지는데, 쟁쟁한 경쟁을 뚫고 살아남은 자들답게 a + b가 모두 동일하다. i번째 팀원으로 선발한 사람의 능력치가 각각 ai, bi라 할 때, 그 팀의 종합 능력치는 (∑i=1kai)×(∑i=1kbi)이다. 팀의 능력치를 최대화하게 지원자들을..

문제 링크https://www.acmicpc.net/problem/26260 문제김소마는 최근에 포화 이진 트리에 대해 배웠다. 포화 이진 트리란, 이진 트리에서 리프 노드를 제외한 모든 노드가 두 자식 노드를 가지며, 모든 리프 노드가 채워진 것을 말한다. 아래의 그림을 통해 쉽게 이해하자.  김소마는 예쁜 포화 이진 검색 트리를 그려 만족했지만, 밥 먹다 흘린 소스가 리프 노드 한 개를 가려버렸다. 여기서 이진 검색 트리란, 모든 왼쪽 자식이 자신보다 작고, 모든 오른쪽 자식이 자신보다 큰 이진 트리를 이야기한다.  그림을 버리려던 찰나, 김소마는 갑자기 포화 이진 검색 트리를 유지하며, 임의의 수를 넣을 때, 트리 구조가 어떻게 바뀔지 궁금해졌다. 멍청한 김소마를 위해 당신이 도와주자. 입력첫 번째..

문제 링크https://www.acmicpc.net/problem/2987 문제백준이는 사과나무가 N개 심어져있는 땅의 일부를 구매했다. 백준이가 구매한 땅은 삼각형이다. 따라서, 어떤 사과나무가 백준이의 것인지 알기가 힘들었다.백준이 땅의 꼭짓점 좌표와 사과나무의 좌표가 주어졌을 때, 백준이 땅의 넓이와 백준이의 사과나무의 개수를 구하는 프로그램을 작성하시오.만약, 어떤 사과나무가 땅의 경계선에 걸쳐있다면, 이것은 백준이 사과나무이다.(xA, yA), (xB, yB), (xC, yC) 로 이루어진 삼각형의 넓이는 다음과 같이 구할 수 있다.|xA(yB - yC) + xB(yC - yA) + xC(yA - yB)| / 2 입력처음 세 개의 줄은 삼각형의 꼭짓점 좌표이다. 다음 줄에는 사과나무의 개수 N이..

문제 링크https://www.acmicpc.net/problem/20956 문제지호는 매일 아이스크림 가게에 방문한다. 아이스크림을 먹던 지호는 놀라 자빠질 수밖에 없었다. 실수로 민트초코 맛을 먹었기 때문이다. 대다수의 사람은 치약 맛이 난다는 이유로 민트초코를 싫어한다. 아이스크림으로 이를 닦는다는 발상은 누가 한 것인지 궁금할 뿐이다. 아무튼 매번 아이스크림을 사 먹는 것이 지겨워진 지호는 이제부터 아이스크림을 훔쳐 먹기로 결심하였다.아이스크림 가게에는 다양한 맛의 아이스크림 N개가 한 줄로 배치되어 있다. 아이스크림에는 번호가 매겨져 있는데, 가장 왼쪽 아이스크림이 1번, 그 오른쪽은 2번, ..., 가장 오른쪽 아이스크림은 N번이다. 지호는 항상 양이 가장 많은 아이스크림을 선택하여 전부 먹는..

문제 링크https://www.acmicpc.net/problem/1715 문제정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친..

문제 링크https://www.acmicpc.net/problem/3055 문제사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과..

문제 링크https://www.acmicpc.net/problem/31671 문제오름은 올라야만 한다.  NLCS Jeju의 기숙사 이름 "오름"은 제주에서 봉우리나 산을 부르는 말인 오름에서 따왔다. 각 기숙사의 학생들은 1년에 한 번, 실제로 기숙사 이름의 기원인 오름을 오르게 된다.오름은 xy 평면에서 세 점 (0, 0), (N, N), (2N, 0)을 잇는 삼각형 모양이다. 당신은 (0, 0)에서 출발해서 (2N, 0)에 도착해야 한다.이동할 때는 (x, y)에서 (x + 1, y + 1) 혹은 (x + 1, y − 1)로만 이동할 수 있다. 또한 이동하여 도착한 위치는 오름의 내부 혹은 경계여야 한다.오름에서 길을 잃기 쉽기 때문에 길을 잃기 쉬운 M개의 지점에 선생님들이 계신다. 하지만 숙제를..

문제 링크https://www.acmicpc.net/problem/9205 문제송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 ..