복습노트 복습노트

문제 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net n개의 보석의 무게와 가격이 주어지고, k개의 가방의 최대 수용 무게가 주어집니다. 이 때 가방은 최대 1개의 보석만 넣을 수 있다고 가정할 때, 도둑이 훔쳐갈 수 있는 최대 가격을 구하는 문제입니다. (n k; for (int i = 0; i > a >> b; v[i].first = a; v[i].second = b; } for (int i = 0..

문제 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 가로의 길이 n(짝수)과 높이 h가 주어지고, n개의 석순과 종유석이 차례대로 주어집니다. 홀수번째는 석순이 주어지고 짝수번째는 종유석이 주어집니다. 이 때 개똥벌레는 1 ~ h의 높이로 날 수 있는데 직진으로 앞에 있는 장애물을 모두 파괴할 수 있습니다. 개똥벌레가 뚫는 장애물의 개수가 최소가 되는 높이와 이 때, 최소의 개수가 총 몇개 있는지 구하는 문제입니다. 예를 들어 n = 6이고 h = 7이고, 장애물이 차례대로 (1, 5, 3, 3, 5, 1)로 ..

문제 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 게임 횟수를 x라 하고, 이긴 게임을 y라고 하고 현재 승률을 z라고 할때 게임을 최소 몇번 더 해야 z가 변하는지 구하는 것이다. 예를 들어 x =10이고, y = 8이면 z = 80이다. 이때 게임을 1번 더하면 x =11, y =9이고, z = 81.xxx %이다. 따라서 최소 1번 더하면 z가 바뀐다. 게임은 항상 이긴다고 가정하자. 수식을 세워보자. 게임을 할 때 마다 무조건 승리하므로 승률은 올라갈 수 밖에 없다. 게임을 진행한 횟수를 k..

문제 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net (왼발, 오른발) 이 처음에 (0, 0)으로 시작해 수열이 주어지면 왼발과 오른발 둘중 아무나 그 위치로 움직여 춤을 추는 점수를 최소로 만드는 프로그램을 만드는 것입니다. 점수는 처음에 (0, 0)에서 아무 곳이나 2점을 얻습니다. 그 다음 발이 인접한 곳으로 이동할 때는 3점을 얻고 정반대인 곳으로 이동하면 4점을 얻습니다. 예를 들어 1에서 2나 4로 갈 떄는 3점을 얻지만, 3으로 갈때는 4점을 얻게 됩니다. 이 문..

문제 11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net 명우와 근우가 카드게임을 한다. n개의 카드가 일렬로 주어지면 명우와 근우가 각자의 턴에 카드 양끝쪽 중 1개를 선택해 카드에 쓰여진 점수를 획득할 수 있다. 이 때 명우가 얻는 점수를 구하면됩니다. 항상 명우가 먼저 카드를 뽑습니다. 명우와 근우는 항상 이기기 위해 최선의 카드를 선택합니다. 예를 들어 n = 4이고 카드가 1, 2, 5, 2 이렇게 주어지면 명우가 얻는 점수는 6입니다. dp로 접근하는 문제인지는 알았지만 점화식을 세우는 데 매우 어려웠습니다..

문제 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 두개의 문자열이 주어지면 공통 부분 문자열이 가장 긴 길이를 출력하면 되는 문제입니다. 예를 들어 ABRACADABRA ECADADABRBCRDARA 두개의 문자열이 주어지면 가장 긴 공통 부분 문자열은 ABRACADABRA ECADADABRBCRDARA 이므로 5를 출력해주면 됩니다. 해당 문제는 최장 공통 부분 수열(Longest Common Subsequence)문제입니다. 하지만 다른 점은 기본적인 lcs는 굳이 문자열이 연속 되지 않아도..

문제 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 현재 사용하고 있는 n개의 메모리 공간과 메모리 제거 비용이 주어지고, 최소 필요한 메모리 공간인 m이 주어지면 n개의 메모리에서 m만큼 제거하면서 최소 비용이 나오게끔 하는 문제입니다. 예를 들어 n = 5이고 n개의 메모리 공간은 {30, 10, 20, 35, 40} 이고, 각각의 메모리 제거 비용은 {3, 0, 3, 5, 4} 라고 하고 m = 60이라 하면, n개의 메모리 중 {30, 10, 20}을 제거하면 제거 비용은 {3, 0, 3} 이므로 총 6이 ..

문제 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 건물의 갯수인 n이 주어지고, n개의 줄만큼 1~n 번 건물의 정보가 주어집니다. 건물의 정보는 [건물을 짓는 시간, 건물을 짓기 위해 먼저 지엉야하는 건물 번호, -1] 이렇게 주어집니다. -1이 나오면 정보가 다 주어졌다는 의미입니다. 각 건물을 짓기 위해 최소 시간을 구하는 문제입니다. 각 건물은 먼저 지어져야 하는 건물이 존재합니다. 물론 없는것도 있습니다. 따라서 이러한 정보를 바탕으로 위상정렬을 사용할 수 있습니다. 또한 "최소 시간"..