문제 링크https://www.acmicpc.net/problem/12738 문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) 출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 예제 입력 1610 20 10 30 20 50예제 출력 14 알고리즘 분류다이나믹 프로..

문제 링크https://www.acmicpc.net/problem/23563 문제루시우는 높이가 H이고 너비가 W인 맵의 시작점에서 끝점까지 이동하려고 한다.맵은 H개의 행과 W개의 열로 이루어진 격자판 모양이다. 각 칸은 벽 또는 빈칸이다.루시우는 상, 하, 좌, 우 방향 인접한 칸으로 한 칸씩 이동할 수 있다. 벽으로는 이동할 수 없다.루시우가 한 칸을 이동하는 데에는 1초가 걸린다.하지만 루시우가 벽을 타고 이동하면 순식간에 (0초의 시간에) 상, 하, 좌, 우 방향 인접한 칸으로 이동할 수 있다.어떤 빈칸의 상하좌우 중 하나가 벽이면 이 칸은 벽에 인접한 칸이라고 한다.벽에 인접한 칸에서 벽에 인접한 칸으로 이동하면 벽을 타고 이동한다고 말한다. 루시우가 맵의 시작점에서 끝점까지 이동하는 데 걸리..

문제 링크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/31871 문제영일랜드는 하나의 정문과 N개의 놀이기구로 이루어진 테마파크로 각각 식별 번호가 매겨져 있다. 정문은 0번, 놀이기구는 1번부터 N번까지의 번호로 구분된다. 정문과 놀이기구 혹은 놀이기구와 놀이기구 사이에는 단방향 간선으로 이어진다. 두 장소를 잇는 간선은 여러 개일 수 있으며 출발 장소와 도착 장소가 같을 수도 있다.영일랜드에 놀러 간 정민이는 영일랜드의 정문에서 출발해 모든 놀이기구를 한 번씩만 탑승하고 정문으로 돌아오는 경로의 최장 시간이 궁금하다. 영일랜드의 놀이기구는 매혹적이어서 안 타고 지나갈 수 없어 각 놀이기구에는 최대 한 번씩만 도달할 수 있다. 또한, 모든 놀이기구를 탑승할 때까지 정문을 경유할 수 없으며 ..

문제 링크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/32281 문제투명한 유리구슬처럼 보이지만그렇게 쉽게 깨지진 않을 거야사랑해 너만을 변하지 않도록영원히 널 비춰줄게 유리구슬로 깨지지 않을 구조물을 만들고자 한다.구조물은 다음과 같은 피라미드 격자의 (x, y)에 유리구슬을 놓아 만들어진다. (x, y는 0 이상의 정수)   y > 0인 좌표의 구조물이 깨지지 않도록 하기 위해서, 구조물은 다음 조건을 충족해야 한다. (x, y)에 유리구슬이 있으려면 (x, y − 1), (x + 1, y − 1)에 모두 유리구슬이 있어야 한다.구조물의 y = 0 부분의 정보가 주어졌을 때, y > 0인 곳에 유리구슬을 적절히 놓아 만들 수 있는 구조물의 유리구슬 개수의 최댓값을 구하여라. 입력첫째 줄에..

문제 링크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/15900 문제평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게임이다.'나무 탈출' 은 N개의 정점이 있는 트리 모양으로 생긴 게임판과 몇 개의 게임말로 이루어진다. 트리의 각 정점에는 1번부터 N번까지 번호가 붙어있다. 1번 정점은 '루트 노드' 라고 불리며, 이 루트 노드를 중심으로 정점 간에 부모-자식 관계가 만들어진다. 자식이 없는 노드는 '리프 노드' 라고 불린다.이 게임은 두 사람이 번갈아 가면서 게임판에 놓여있는 게임말을 움직이는 게임이다. 처음에는 트리의 모든 리프 노드에 게임말이 하나..

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