본문 바로가기

전체 글

 (265)
백준11502 - 새 개의 소수 문제 https://www.acmicpc.net/problem/11502 11502번: 세 개의 소수 문제 문제 정수론(수학)에서, 세 개의 소수 문제(3-primes problem) 는 다음과 같은 추측을 말한다. '5보다 큰 임의의 홀수는 정확히 세 개의 소수들의 합으로 나타낼 수 있다. 물론 하나의 소수를 여러 번 �� www.acmicpc.net 1000이하의 소수를 구한 뒤 벡터에 저장하고 이 벡터를 이중 포문으로 순회하며 특정수에서 뺀 수가 소수이면 출력을 해주는 문제이다. 오름차순으로 출력해야 되고 중복된 원소를 사용할 수 있어 multiset을 이용하였다. #include #include #include using namespace std; int mat[1001]; vector v; void ..
백준2696 - 중앙값 구하기 https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 문제 어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오. 예를 들어, 수열이 1,5,4,3,2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번 www.acmicpc.net 트리를 이용한 자료구조이다. 중복된 원소를 입력 받기 위해서 multiset을 이용하였다. 중앙값을 구하면 되는데 중앙값은 평균이 아니고 주어진 수열에서 오름차순이나 내림차순으로 배열하였을 때 가장 중앙에 위치한 원소를 가리켜 말한다. 따라서 set이나 multiset은 입력과 동시에 오름차순으로 정렬해주기 때문에 이 문제에 적합하다고 생각하였다. #include #include..
백준11501 - 주식 https://www.acmicpc.net/problem/11501 11501번: 주식 문제 홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다. 주식 하나를 산다. 원 www.acmicpc.net 생각의 전환이 필요한 문제였다. 현재 주식값보다 제일 비싸지는 미래의 값을 찾아서 가장 이득이 많이 남을때 팔아버리면 되지만 앞에서부터 큰 값을 찾아가는 과정은 너무 시간이 오래걸렸다. 따라서 가장 먼 미래인 맨 뒤에서부터 이득이 가장 커지는 경우를 찾아가면 되었다. 현재 최대 주식 차익을 결정하기 위해서 가장 우선적으로 가장 먼 미래의 값을 찾아 점점 가까운 미래로 접근하면서 가장 이득이 클 때를..
백준16162 - 가희와 3단 고음 https://www.acmicpc.net/problem/16162 16162번: 가희와 3단 고음 첫째 줄에 참가자들의 음의 개수를 나타내는 정수 N(1 ≤ N ≤ 2 x 104), 고음의 첫 항과 공차를 의미하는 정수 A, D(1 ≤ A, D ≤ 107)가 공백으로 구분되어 주어진다. 둘째 줄에 참가자들의 음을 �� www.acmicpc.net 그리디를 이용하여 풀었다. 초항을 먼저 찾아 벡터에 넣은 후 공차 만큼 더한 숫자를 차례대로 찾아가서 해당하는 수를 차곡차곡 벡터에 넣어서 길이를 출력하면 된다. #include #include using namespace std; int main() { int N, A, D; int x; int next; vector v; cin >> N >> A >> D;..
백준18353 - 병사 배치하기 https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net LIS로 해결하면 되는 문제이다. 연속되게 작아지는 수열을 찾으면 되기 때문에 일반적인 LIS문제와 조금 다르지만 입력한 숫자에 마이너스를 붙여서 비교하면 내림차순도 찾을 수 있기 때문에 LIS로 해결하였다. #include #include #include #define INF 987654321 using namespace std; int main() { int n, x; vector ..
백준1240 - 노드사이의 거리 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 노드와 간선에 관한 비용 문제였다. 문제에서 트리는 노드들이 서로 양방향으로 연결되어 있고 최대 1000개의 노드를 가진다. 따라서 1001개의 벡터를 선언하고 1001 X 1001개의 서로 다른 노드를 연결 하였을 때 드는 비용을 저장하였다. 노드의 대한 정보를 입력 받은 후에 bfs를 이용하여 내가 출발한 노드에서 도착한 노드까지의 비용을 출력하면 된다. #include #include #include #define MAX 1001 usi..
백준11607 - Grid https://www.acmicpc.net/problem/11607 11607번: Grid Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains two space-separated integers n and m (1≤n,m≤500), indicating the size of the grid. It is guaranteed that a www.acmicpc.net 다익스트라를 이용하여 푼 문제이다. 왼쪽 맨 위에서 오른쪽 맨 아래까지 최소 몇 번 만에 이동하는지 구하는 문제이다. bfs를 이용하..
백준9753 - 짝 곱 https://www.acmicpc.net/problem/9753 9753번: 짝 곱 문제 정수 K (1 ≤ K ≤ 100,000)가 주어진다. 이때, K보다 크거나 같은 서로 다른 소수의 곱 중에서 가장 작은 곱을 찾는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 20)이 주어진다. 다음 T개 줄에는 K가 한 줄에 하나씩 주어진다. 출력 각각의 K마다 K보다 크거나 같은 서로 다른 두 소수의 곱 중에서 가장 작은 곱을 출력한다. 예제 입력 1 복사 5 1 3 10 300 100000 예제 출력 1 복 www.acmicpc.net 에라토스테네스의 체와 이분 탐색을 이용하여 해결한 문제이다. K가 10만으로 주어졌을 때 100001을 출력하기 때문에 50001까지의 소수..

티스토리툴바