728x90 반응형 C++5 [백준 3661번 C++: 생일 선물] 문제링크우선 케이스를 단순하게 3개로 먼저 나누었습니다.선물 금액 > 낼수있는 비용의 총합선물 금액을 모두 공평하게 낼 수 있는 경우나머지 경우우선적으로 3번 째 경우 공평하게 나눈 비용과 낼 수 있는 비용 중에 우선적으로 작은 값을 설정하고, 더 낼 수 있는 사람들을 추려냈습니다. 위 조건에서 금액 분배하는 방법에서 리스트 앞에 있는 사람이 돈을 더 내야하므로 따로 cmp()를 작성해서 여유 비용이 같을 경우 인덱스가 작은 것이 먼저 오도록하여 공평하게 나눌 수 있도록 했습니다.#include #include #include #include using namespace std;bool cmp(pair a, pair b){ if(a.first == b.first){ return a.se.. 2024. 8. 9. [백준 16465번 C++] Bookend 문제링크를 통해서 자세한 문제 조건을 확인하실 수 있습니다.위 그림의 2번을 제외한 케이스들 이외에 Bookend가 가능한 경우가 없습니다. #include using namespace std;int main(){ int n,m,l; cin >> n >> m >> l; int totalwidth = 0; for(int i = 0; i > b; totalwidth += b; } if(m==totalwidth) cout =l) cout 2024. 8. 7. [백준 12143번 C++: 영어와 프랑스어(small)] 문제 링크를 통해서 자세한 문제를 확인하실 수 있습니다.문제를 보면 영어 단어와 프랑스어 단어를 주어주고 추가적인 문장을 통해서 영어와 프랑스어에 둘다 포함되는 단어의 최소의 개수를 구하는 것입니다. 처음 브루트포스로 풀려다가 시간초과와 많은 문제를 접하고.. 접근 방법을 다르게 해보자 마땅한 알고리즘이 있는가 찾아보다가 Max Flow Min Cut 알고리즘 중 에드몬드-카프 알고리즘을 사용해서 문제를 풀 수 있었습니다. 위의 블로그에서 가져온 핵심 알고리즘입니다.블로그에서 그림으로 쉽게 설명해놓아서 직접 가서 보셔도 됩니다. 저는 영어 단어의 집합과 프랑스어 단어의 집합으로 분리를 시키는 과정에서 두개 모두 포함된 단어들의 정점들은 제거하면 되겠다는 생각이 들었습니다. 우선적으로 최대 유량을 구하.. 2024. 8. 3. [백준 26075번 C++: 곰곰아 선넘지마] 문제링크를 통해서 자세한 조건들을 확인하실 수 있습니다.연산의 횟수를 알기 위해서 각각의 주어진 입력에 대한 1의 위치를 각각 저장하고, s에 1의 위치와 t에 1의 위치의 차이의 총 합을 구합니다. 결국 이 총합의 값은 S와 T의 위치를 바꾸기 위해 실행된 연산의 총 횟수 입니다. 여기서 S에서 수행한 연산 횟수를 a라고하고, T에서 수행한 연산 횟수를 b라고 하고, dist의 총합을 임의의 값인 V라고 한다면 아래의 식으로 표현할 수 있습니다.$$ a + b = V $$ 이문제에서 구해야할 답은 즉 아래의 식의 최소값입니다.$$ a^{2} + b^{2} $$위의 값이 최소가 될려면 a와 b가 동일한 값이어야 합니다. 이에 대한 증명은 아래에서 확인하실 수 있습니다.더보기 $$ a + b = S $$.. 2024. 8. 3. [c++][BOJ 11692 시그마 함수] 문제 풀이 [문제 링크](https://www.acmicpc.net/problem/11692)문제는 입력값까지의 범위에 대한 약수의 합을 구하는 문제이다.약수의 합 공식은 나무위키에서 확인 할 수 있습니다.$$ a = b^{n}\times c^{m}$$어떤 자연수 a에 대해서 b,c로 소인수 분해를 했을 경우 각각의 지수를 통해서약수의 개수는 아래의 식을 통해 구할 수 있습니다$$ (n+1)\times(m+1) $$약수의 총합은 아래의 식을 통해 구할 수 있습니다.$$ (1 + b^{1} + \cdots +b^{n}) \times (1 + c^{1} + \cdots + c^{m}) $$해당 식을 통해서 1부터 주어진 M까지의 범위 중 합이 짝수인 것을 찾으면 해결됩니다.곱해서 짝수와 홀수가 나타나는 경우는 소인수.. 2024. 7. 23. 이전 1 다음 728x90 반응형
