본문 바로가기

Algorithm9

[C/C++] 2805 :: 나무 자르기 👉 문제 링크https://www.acmicpc.net/problem/2805 2805번: 나무 자르기첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보www.acmicpc.net  👉 문제👉 접근방식 & 주의할점이번 문제는 랜선 자르기 문제와 풀이 방식이 유사한 문제이다.이 문제를 풀기 전에 되도록이면 아래의 문제를 먼저 보고 오는 것을 추천한다.위의 문제를 먼저 풀고 오면 이 문제도 자연스럽게 풀릴 것이다. https://onlyoliy.tistory.com/entry/CC-1654-%EB%9E%9C%EC%84%A0-.. 2022. 10. 26.
[C/C++] 1654 :: 랜선 자르기 (이분탐색) 👉 문제 링크https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그www.acmicpc.net  👉 문제👉 접근방식  & 주의할 점이분탐색을 이용한 문제로 백준 2805번 나무자르기 와 비슷한 맥락의 문제이다. 알고리즘1. low의 값을 1, high를 랜선들 중 가장 긴 길이로 지정한다.2. mid값을 구하고, 몇개의 랜선을 만들수 있는지 이분탐색을 이용하여 구한다.(1) 만들수 있는 랜선의 수가 요구되는 랜선수보다 많거나 같다면(count >=.. 2022. 10. 26.
[C/C++] 2512번 :: 예산 (이진탐색) 👉 문제 링크https://www.acmicpc.net/problem/2512 2512번: 예산첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상www.acmicpc.net👉 문제 👉 접근방식 이분 탐색을 사용하는 문제들 중 경로가 가장 확실하게 보이는 문제였다.mid 를 count 로 두고 sum값을 매번 구해서 M과 비교하여 count값을 구해내는 문제다.  👉 코드#include #include #define MAX_COUNT 10000using namespace std;int N, M;int arr[MAX_COUNT];void bsearc.. 2022. 10. 22.
[C++] 2581::소수 링크https://www.acmicpc.net/problem/2581 2581번: 소수M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.  단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.www.acmicpc.net  문제자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다. 접근방식 & 주의할점m부터n까지 수를for문을 사용해서 하나씩.. 2022. 10. 9.
[C++] 1292::쉽게 푸는 문제 링크 https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 문제 동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다. 이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다. 하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자. 동호야 니문제.. 2022. 10. 8.
[C++] 1978::소수찾기 링크 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 1978::소수찾기 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 접근방식 n을 입력받은 뒤 차례로 n개의 수를 입력받고 각 숫자를 1부터 나누기 했을때 약수의 개수가 2개인 소수의 개수를 찾아내었다. 주의할 점 1. 1부터 1씩 키워가며 약수를 구하는 과정에서 nums[i]본인까지 나누어주어야 한다. > n; int * num = new int[n]; //올바른 코드 int n; cin >> n; int nums[n];.. 2022. 10. 8.
[C++] 2693번::N번째 큰수 문제링크 https://www.acmicpc.net/problem/2693 2693번: N번째 큰 수 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 배열 A의 원소 10개가 공백으로 구분되어 주어진다. 이 원소는 1보다 크거나 같고, 1,000 www.acmicpc.net 문제 배열 A가 주어졌을 때, N번째 큰 값을 출력하는 프로그램을 작성하시오. 배열 A의 크기는 항상 10이고, 자연수만 가지고 있다. N은 항상 3이다. 접근방식 T를 입력받아서 2차원 배열을 동적할당해주기만 하면 어렵지 않은 문제였다. 그 뒤로는 sort 함수를 사용하여 오름차순 정렬을 하고 출력만 하면 된다. 주의할 점 C++에서 동적할당은 C언어와 달리 m.. 2022. 10. 7.
[C++] 2609번 최대공약수 최소공배수 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 접근방식 입력받는 두 수를 N1, N2라고 할 때 그 중 큰수를 commonMultiple, 작은수를 commonDivisor 값에 넣는다. commonDivisor 값을 1씩 줄여가며 최대공약수를 찾아내고 commonMultiple 값을 1씩 늘려가며 최소공배수를 찾아냈다. 코드 #include using namespace std; //backjoon 2609 최대공약수.. 2022. 10. 7.
[C++] 2309_일곱난쟁이 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 접근방식 9명의 난쟁이의 키를 받아서 거직 난쟁이 둘을 걸러 7명 난쟁이 키의 합이 100이 되도록 하는 문제이다. 우선 sort함수를 사용하여 오름차순 정리를 해주었다. 7명의 난쟁이의 키의 합이 100인 걸 구하는게 아니라 반대로 9명의 난쟁이 키의 합에서 100을 빼서 dif에 저장한 뒤, 두명의 난쟁이(a,b) 키의 합이 dif와 같아지는 값을 찾아서 답을 구하였다. 코드 #include #incl.. 2022. 10. 6.

티스토리툴바