복습노트 복습노트

문제 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 예를 들어 동전이 3개 주어지고, 각각 1, 5, 12 이고, k = 15이면 정답은 3이다. 전형적인 배낭 문제이다. int []coin = new int[n+1]; int []dp = new int[k+1]; for(int i=..

문제 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 4 * 4 크기의 칸에서 1 ~ 16번까지의 물고기가 들어간다. 처음 상어는 [0][0]에서 물고기를 먹고 물고기는 이동한다. 물고기가 이동하면 상어는 방향에 따라 갈 수 있는 공간에서 물고기를 하나 먹을 수 있다. 이러한 반복을 상어가 물고기를 못먹을 때 까지 반복한다. 정리하면 다음과 같다. 1. 상어는 물고기를 먹을 수 있으면 먹는다. 2. 1번 물고기 부터 시작해서 16번 물고기 까지 이동을 한다. 만약 이동을 못하게 되면 45도 반..

문제 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net n개의 서로 다른 금액의 동전이 주어지면 동전을 조합해서 m의 금액이 나올 수 있는 경우의 수를 구하는 문제이다. 예를 들어 n은 3이고 서로다른 동전은 2, 3, 5라고 할 때 m = 10이면 정답은 4가 된다. {2, 2, 2, 2, 2}, {2, 2, 3, 3}, {2, 3, 5}, {5, 5} 여러 규칙을 찾으려 노력했지만 이러한 문제 유형은 배낭 문제이다. 위에 예시를 기반으로 표를 만들면 다음과 같다. 이를 코드로 구현하면 아래와..

문제 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net 왼쪽 그림과 같이 n개의 노드가 주어지면 트리를 형성할 수 있다. 트리는 연속된 숫자여야 한다. 연속된 숫자는 하나의 집합이다. 연속된 숫자가 아니면 다음 집합으로 넘어간다. 이 때 K가 주어지는데 K의 사촌 수를 구하는 문제이다. 사촌 이란 두 노드의 부모는 다르지만, 두 부모가 형제(sibling)일 때 두 노드를 사촌이라고 한다. n개의 수는 오름차순으로 주어진다. 왼쪽의 예시는 1, 3, 4, 5, 8, 9, 15, 30, 3..

문제 18116번: 로봇 조립 성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 www.acmicpc.net 명령어는 I 또는 Q가 주어진다. I가 주어질 경우 노드 2개가 추가로 주어진다. 예를 들어 I 1 2 라면 1번 노드와 2번 노드를 연결한다는 것이다. Q가 주어질 경우 노드 1개가 추가로 주어진다. 예를 들어 Q 1이라면 1번 노드가 포함된 그래프의 노드 개수를 구해주면 된다. 즉 1번과 2번이 연결되있으므로 정답은 2가 된다. 노드를 서로 합치는 것이기 때문에 union-find 알고리즘을 사용하였다. 연결하는 것은 쉬운데 어떻게 같은 집합의 노드 개수를 ..

문제 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 처음에 n개의 {문제번호, 문제 난이도} 가 주어진다. 위에 규칙에 따라 구현해주면 된다. 명령어 recommend는 추천 문제 리스트에 문제가 하나 이상 있을 때만 주어진다. 명령어 solved는 추천 문제 리스트에 문제 번호가 하나 이상 있을 때만 주어진다. 먼저 생각난것이 이중 우선순위큐를 돌리자고 생각했다. 새로운 클래스를 만드는 것이다. class Hard implements Comparable { int num; in..

문제 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 임의의 두 노드에서 모두 도달할 수 있는 그래프가 주어지고 각 노드 사이에는 비용이 있는 간선이 주어진다. 이 때 그래프를 둘로 나눈다. 나눈 각각의 그래프는 서로 연결되어 있어야 하고 간선의 합이 최소여야 한다. 두 그래프의 각각의 간선의 합이 최솟값을 구해라. 그래프는 최소 1개의 노드가 존재해야 한다. 문제를 잘보면 크루스칼 알고리즘을 사용하는 것을 알 수 있다. 하지만 어떻게 2개로 나눌까?? 잘 생각해보면 간단..

문제 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net N개의 기차가 어둠을 헤치고 은하수를 건너려고 한다. 기차는 20개의 일렬로 된 좌석이 있고, 한 개의 좌석에는 한 명의 사람이 탈 수 있다. 기차의 번호를 1번부터 N번으로 매길 때, 어떠한 기차에 대하여 M개의 명령이 주어진다. 명령의 종류는 4가지로 다음과 같다. 1 i x : i번째 기차에(1 ≤ i ≤ N) x번째 좌석에(1 ≤ x ≤ 20) 사람을 태워라. 이미 사람이 타있다면 , 아무런 행동을 하지 않는다. 2 i x : i번째 기차..