본문 바로가기

개발

 (72)
보석 문제 세계적인 도둑 동현이는 보석점을 털기로 결심했다. 동현이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 동현이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 각 가방에는 최대 한 개의 보석만 넣을 수 있다. 동현이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (1 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000) 모든 숫자는 양의 정수이다. 출력 첫째 줄에 동현이가 훔칠 수 있..
풍선 문제 큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다. 진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다. 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다. 높이는 임의로 선택한다. 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다. 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다. 우리의 목표는 모든 풍선을 터트리되 가능한한 적은 화살을 사용하는 것이다. 입력 첫 번째 줄에는 정수 N(1 ≤ N ≤ 1 000 000)이 들어온다. 두 번째 줄에는 배열 Hi가 N개 들어온다. 각각의 Hi(1 ≤ H..
지은이가 지은 집 문제 최근에 지은이는 건축에 관심이 많아 집을 짓게 되었다. 태양이는 지은이가 지은 집에 놀러갔다. 근데 아니나 다를까 집에 작은 구멍이 있는 것이다. 지은이와 태양이는 집을 보수하기로 했다. 다행히도 지은이가 집을 짓다가 남은 재료가 남아서, 이를 이용하여 집을 보수하기로 했다. 구멍이 난 곳의 너비는 x센티미터이다. 태양이와 지은이는 사이가 너무 좋아서, 남은 재료 중 하나씩 골라서 이어 붙이고, 이로 구멍을 막기로 했다. 즉, 태양이과 지은이가 고른 재료의 길이가 L1, L2이면, L1+L2가 x와 같아야 구멍을 막을 수 있다. 크기가 다르면, 또 망가질 위험이 있기 때문이다. 그럼 이제 구멍을 완벽하게 막을 수 있는 두 막대를 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 구멍의 너비 X가 주..
가장 많은 수 문제 N개의 정수가 주어진다. 이 중 가장 많이 등장하는 수를 구하시오. 만약 이런 수가 여러 개라면 작은 수를 출력하세요. 시간제한: 1초 입력 첫째 줄에는 정수의 개수 N이 주어진다. (1
소수경로 문제 형석이는 다음날 SDS에 강의를 하러 간다. 하지만 아침에 일찍 일어나야 한다는 부담감에 고급 알람 시계를 준비하였다. 최근에 화장실 사진찍기, 뺨 때리기, 냄새 뿌리기 등의 알람 시계가 나오고 있지만, 형석이는 강의를 위해 머리를 써야 끌 수 있는 알람을 준비하였다. 이 시계의 시간을 맞춰 놓고, 그 시간이 되어 울리기 시작하면, 4자리의 소수 2개가 고급 알람 시계에 표시된다. 첫 번째 적혀 있는 수는 숫자를 변경할 수 있게 되어있다. 그럼 이제 알람을 끄는 방법은 간단하다. 첫 번째 적혀 있는 소수를 두 번째 적혀 있는 소수로 변경하면 된다. 이때, 한번에 한자리만 변경할 수 있고, 한자리를 변경하였을 때, 변경된 수는 소수이어야 한다. 또한 4자리 소수이기 때문에, 경로 중간에도 4자리를 유..
N-Queen 문제 N-Queen문제는 유명한 문제이다. 이는 N × N인 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하시오. 입력 첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 12) 출력 첫 번째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 힌트 예제 입력 4 예제 출력 2 #include /* run this program using the console pauser or add your own getch, system("pause") or input loop */ void NQueen(); int findQueen(int N, int W, int Check1[], int Check2[], int Check3[]); in..
ASSEMBLY LINE SCHEDULING 문제 명우네 공장에는 두 개의 생산라인이 있고, 각 라인에는 n개의 공정이 순서대로 있다. 하나의 제품이 완성이 되려면 두 생산라인 중 한 생산라인을 정해, 그 생산라인에 미완성 제품이 들어가고 그 생산라인의 n개의 공정을 순서대로 지나, 생산라인에서 생산을 마무리하여 완성된다. 중간에 생산라인을 바꿀 수도 있다. 첫 번째 생산라인의 i번째 공정에서 소요되는 시간은 S1,i이고, 두 번째 생산라인의 i번째 공정에서 소요되는 시간은 S2,i이다. 그리고 첫 번째 생산라인에 진입하는 시간은 e1, 두 번째 생산라인에 진입하는 시간은 e2이고, 첫 번째 생산라인에서 생산을 마무리 하는 시간은 x1, 두 번째 생산라인에서 생산을 마무리 하는 시간은 x2이다. 마지막으로 첫 번째 생산라인의 i번째 공정을 마치고 ..
막대기 자르기 문제 길이가 N인 막대기가 있다. 막대기를 길이가 자연수가 되도록 여러 조각으로 자를 수 있다. 각 길이에 대해 값어치가 있을 때, 값어치 합이 최대가 되도록 막대기를 자르자. 예를 들어, 길이가 4인 막대기가 있고 각 길이 별 값어치가 아래와 같다고 하자. | length | 1 | 2 | 3 | 4 ||----------|---|---|---|---|| cost | 1 | 5 | 8 | 9 | 이 때, 길이 2인 막대기가 두 개가 되도록 전체 막대기를 자를 경우 전체 값어치가 10 되어 최대가 된다. 입력 첫 줄에 막대기의 길이 N이 주어진다. (1≤N≤3,000) 둘째 줄에 N개의 자연수가 공백으로 구분되어 주어지는데, i번째로 주어지는 수는 길이가 i인 막대기의 값어치를 의미한다. 이 때 주어지는..

티스토리툴바