난이도 : 골드 5 걸린 시간 : 1시간 반 이상 문제 문제 바로가기 오답 처음에 완전탐색으로 하되 최대한 조합의 범위를 줄여서 구현해보았다. 하지만, 시간 초과로 실패..! #include #include #include #include using namespace std; // 6시 4분 시작 => 6시 42분 중단, 11시 12분 시작 => // N > K; for (int i = 0; i > w >> v; vec.push_back(make_pair(w, v)); } // 무게 순 정렬 sort(vec.begin(), vec.end(), compare); // 무게는 같은데 가치가 작은 것은 없애기 for (int i = 1; i < vec.size(..

난이도 : 골드 3 걸린 시간 : 50분 문제 문제 바로가기 풀이 처음에 풀이를 이상하게 생각해서 O(n^3)의 완전탐색 혹은 DP를 사용하는 법을 생각하고 있었다. 그러다가 생각을 다시 해보니 쉽게 풀 수 있는 방법이 있어 20분만에 풀게 되었다. 역시 처음에 풀이를 주석으로 쭉 적어본 후 예제를 테스트 해보고 수행하는 것이 제일 정확하고 알맞은 방법인 듯 하다. 입력의 범위는 10^3로 그다지 높은 편은 아니었지만, 완전탐색 시 O(n^3)이 걸리므로 충분히 시간초과가 나올 수 있는 범위였다. 또한 각 숫자의 범위도 최대 10^3이므로 숫자를 하나씩 내려가며 / 올려가며 푸는 완전탐색 또한 불가능했다. 예제의 힌트를 보니 연속적이지 않은 수열의 흐름도 가능했고, 그렇다면 각 숫자가 보유하고 있는 ma..

ABCDE https://www.acmicpc.net/problem/13023 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 512 MB 6509 1863 1222 28.399% 문제 BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다. 둘째 줄부터 M..

음하철도 구구팔 https://www.acmicpc.net/problem/1393 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 445 64 57 29.082% 문제 최백준은 음하철도 구구팔에 탔다. 문제는 구구팔의 기장인 조교 김재홍이 반쯤 미쳐서 열차를 멈추지 않는다는 것이다. 그래서 최백준은 달리고 있는 열차에서 뛰어내려야 한다. 그런데 뛰어내릴 때 정류장 까지 거리가 너무 멀면 마이 아플 수 있다. 그래서 철도가 정류장에 가장 많이 근접했을 때 뛰어내리고자 한다. 어디서 뛰어내려야 하는가? 입력 첫째 줄에는 정류장의 위치 x y가 주어지고, 둘째 줄에는 현재 열차의 위치 X Y와 열차가 초마다 이동하는 x좌표 y좌표가 주어진다. 열차는 항상 직선으로 움직인다. 주어지는..

동물원 문제 어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다. 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다. 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다. 입력 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. 출력 첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라. 예제 입력 1 4 예제 출력 1 41 나의 답 코드 N 입력 받기 sum = 1+2..

도서관 https://www.acmicpc.net/problem/1461 문제 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다. 입력 첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 ..

LCS 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 19827 8068 6050 41.148% 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 알고리즘 분류 다이나믹 프로그래밍 나의 답 생각의 흐름 완전탐색 조건 줘도 시간 초과 다이나믹 프로그래밍 우선 완전탐색을 구현할 때는 s..

RGB 거리 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 0.5 초 (추가 시간 없음) 128 MB 42269 19789 14882 47.682% 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 ..