투투

문제 앞으로 N일간 주식 가격이 숫자로 주어진다. 이 중 K번 거래를 하려고한다. 거래를 할 때는 하루에 한 번만 할 수 있으며 첫 날을 제외하고 이전날보다 주식가격이 올랐을 때만 거래를 한다. 이 때 K번 거래를 할 수 있는지 검사하는 프로그램을 작성하시오. 입력 입력 파일에는 여러 테스트 메이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두 정수 N과 K이 주어진다. N은 앞으로 주가를 알 수 있는 날 수이며, (1 ≤ N ≤ 10,000) K는 거래의 회수이다. (1 ≤ K ≤ 10,000) 다음 줄에는 앞으로 N 날의 주가가 사이에 공백을 두고 주어진다. 주가는 1부터 10,..

문제 어린이집에 N명의 학생이 있고 소풍을 가려고한다. N명의 학생에게 1번부터 N번까지 번호를 부착하였고 학생들을 보호하기위해 번호순서대로 일렬로 서서 걸어가도록 하였다. 중간에 학생들의 번호순서가 바뀌었다. 이때 학생들을 이동시켜서 원래 번호순서대로 다시 줄 세우기위해서는 최소한 몇 명의 학생을 이동시켜야하는지 구하라. 입력 첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다. 출력 첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다. 접근 예전에 크루스칼이나 프림을 적용하는 문제를 풀 때 최소신장트리를 구성해야한다는 것을 파악하면 쉽게 풀 수 있었다. 이번 문제에서도 LIS를 구하는..

문제 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로..

문제 수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열을 구하라. 입력 첫째 줄에 수열의 크기 N이 주어진다. 둘째 줄에는 N개의 수를 갖는 수열이 주어진다. 출력 첫째 줄에 가장 긴 증가하는 부분 수열의 길이를 출력하고 둘째 줄에 가장 긴 증가하는 부분 수열을 출력한다. 접근 가장 긴 증가하는 부분수열을 구하는 것을 LIS 알고리즘이라 하고 완전 탐색, 동적 계획법, 이진 탐색의 방법이 있다. 이 문제에서는 동적 계획법으로 접근을 했다. {10 20 10 30 20 50}이라는 수열이 있을 때 30까지의 증가하는 부분수열을 구해보자. 이전에 20의 증가하는 부분수열의 길이는 2이다. - 10과 30을 비교했을 때 30이 더 크다. - 이제 증가하는 부분수열은 10+30로 길이는 2이다. 원래 10만 ..

문제 NxN 크기의 땅이 있고 1X1개의 칸으로 나누어져있다. 각각의 땅에는 나라가 존재하고 몇 명이 사는지 알 수 있다. 인구이동이 시작할 때는 다음과 같이 진행되고 인구 이동을 할 수 없을 때까지 반복한다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다. 연합을 해체하고, 모든 국경선을 닫는다. 각 나라의 인구수가 주어졌을 때..

문제 빨간색, 파란색, 노란색, 녹색의 네 가지 색이 있는 카드가 있고 각 색깔별로 1부터 9까지 숫자가 쓰여져있다. 총 36장의 카드에서 5장의 카다를 뽑고 아래와 같은 규칙으로 계산한다. 1. 카드 5장이 모두 같은 색이고 숫자가 연속될 때 가장 높은 숫자에 900을 더한다. 2. 카드 5장 중 4장의 숫자가 같을 때 점수는 같은 숫자에 800을 더한다. 3. 3장의 숫자가 같고 2장의 숫자도 같을 때 3장이 같은 숫자에 10을 곱하고 2장이 같은 숫자를 더한 다음 700을 더한다. 4. 5장의 숫자가 연속적일 때 점수는 가장 높은 숫자에 600을 더한다. 5. 카드 5장의 숫자가 연속적일 때 가장 높은 숫자에 500을 더한다. 6. 3장의 숫자가 같을 때 점수는 숫자에 400을 더한다. 7. 2장의..

문제 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n개의 트럭이 건너가려고 한다. 다리 위에는 w대의 트럭만 동시에 올라갈 수 있고 다리의 길이는 w 단위길이, 각 트럭들은 하나의 단위시간에 하나의 단위길이만큼 이동할 수 있다. 또한, 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L이하여야한다. 다리의 길이와 다리의 최대하중, 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때 모든 트럭이 다리를 건너는 최단시간을 구하라. 입력 첫째 줄에 트럭의 수 N, 다리의 길이 W, 다리의 최대하중 L이 주어진다. 두 번째 줄에는 트럭의 무게가 N개 주어진다. 출력 모든 트럭들이 다리를 건너는 최단시간을 출력한다. 접근 처음에는 주어진 예시를 통해 직접 그려보면서 시..

문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다. 최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다. 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번..

문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고있다. 이 N명의 학생이 X번 마을에 모여서 파티를 하려고한다. 마을 사이에는 총 M개의 단방향 도로들이 있고 이 도로들을 지나갈 때는 T만큼의 시간이 소비된다. 각각의 학생들이 각자의 마을에서 X번 마을로 파티하러왔다가 다시 돌아갈 때 걸리는 시간이 가장 오래걸리는 시간이 몇인지 구하라. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다. 출력..

문제 어떤 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져있다. 각 길은 유지비가 들고있으며 마을을 두 개의 마을로 분할할 계획을 갖고있다. 마을에는 집이 하나 이상 있어야하고 분리된 두 마을 사이에 있는 길들도 필요없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있을 때 나머지 길 유지비의 합을 최소로 되도록 하라. 입력 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는..