복습노트 복습노트

문제 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net n개의 동전이 주어지면 동전의 조합을 이용해 k원이 되는 경우의 수를 구하는 것입니다. 동전은 무한대로 쓸 수 있습니다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우입니다. 예를 들어 n = 3이고 동전의 가치가 각각 1, 2, 5이고 k = 10이면 동전의 조합을 통해 10이되는 경우의 수는 10입니다. 처음에 봤을 떄 knapsack 문제와 비슷한 느낌을 받아 이차원 배열을 만들고 생각해봤습니다. 먼저 1원으로 1 ~ 10원을 만드는 경우의..

문제 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net n일의 여름방학이 주어지고, m번의 바쁜날이 주어지면 여름방학동안 리조트 이용을 바쁜날을 제외하고 매일 할 떄 최소비용을 구하는 문제입니다. 위의 표의 첫번째 행은 여름방학의 날을 의미합니다. 검은색은 바쁜날입니다. 두번째 행과 세번째 행은 각각 비용입니다. 두번째 행은 7만원이 들고, 세번째 행은 62000원이 들어서 최소비용은 62000원입니다. 쿠폰을 3개 모으면 하루 이용권이 무료로 제공됩니다. 쿠폰의 여부에 따라 최소비용을 결정하는 것이 까다로웠습니다. 그래..

문제 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 위와 같은 괄호가 주어졌을 때, 괄호가 바로 ()이면 레이져이고, '('는 쇠막대기의 시작점, ')'는 쇠막대기의 끝점입니다. 레이져를 쏘았을 때 쇠막대기의 조각을 세는 문제입니다. 위의 그림에서는 17개 입니다. 처음에는 레이저의 좌표와 쇠막대기의 좌표를 기록해 하나하나 비교해가면서 레이져가 쇠막대기를 겹치는 부분을 세었습니다. 물론 정답은 맞았지만, 시간이 매우 오래 걸렸습니다. (O(n^2)) 새로운 방법은 '(' 가 나오면 무조건 스택에 넣어줍니다. 그러다가 레..

문제 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로 접근하는 문제인지는 알았지만 점화식을 세우는 데 매우 어려웠습니다..