https://www.acmicpc.net/problem/10244 10244번: 최대공약수들 n개의 수로 이루어진 수열 A가 주어질 때, 1≤lo≤hi≤n의 정의역을 가지는 함수 f(lo,hi)는 Alo부터 Ahi까지 모든 원소들의 최대공약수로 정의된다. lo와 hi는 수열의 원소가 아닌 인덱스라는 점에 주 www.acmicpc.net 구간 l ~ r 까지의 원소들의 최대공약수를 구했을 경우, 나올 수 있는 정수의 개수를 구하는 문제이다. 우선 주어지는 원소는 100 이하의 자연수이므로, 최대공약수의 개수도 최대 100개임을 알 수 있다. 하지만 i ~ n까지의 부분 집합을 하나하나 계산하기에는 시간적인 문제가 있으므로 이를 완전 탐색으로 접근하기에는 무리가 있어 보였다. 그래서 생각한 것은 1 ~ 1..
전체 글
spypsyA - Scoreboard n개의 점수가 주어지고, 각 점수의 최종 합이 더 큰 사람을 출력하는 문제 1 2 3 4 5 6 7 8 9 10 11 12 #include using namespace std; int main() { int n, x, y, a=0, b=0; cin >> n; for (int i = 0; i > x >> y; a+=x, b+=y; } if (a > b) cout
A - Long Loong n이 주어졌을 때, L, o, n, g로 이루어진 문자열을 출력하는 문제 문자열의 길이는 n + 3이고, 문자열 중 o의 개수가 n개여야한다. 간단하게 L을 출력하고, n개의 o를 출력하고, ng를 출력시키면 된다. 1 2 3 4 5 6 7 8 #include using namespace std; int main(){ int n; cin >> n; cout n; while(1){ cnt*=5; if(cnt>n){ cnt/=5; break; } } check(n, cnt); cout n; for(int i=1; i> dp[i]; for(int i=1; i=0; i--) r[i]=min(r[i+1]+1, dp[i]); for(int i=1; i
https://www.acmicpc.net/problem/2374 2374번: 같은 수로 만들기 n(1 ≤ n ≤ 1,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다. 이 자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가한다. 이때, A[i]만 증가하는 것이 아니고, A[i]의 좌우로 인접한 같은 수의 그룹이 한 www.acmicpc.net 배열의 원소를 1씩 더하는데, 인접한 수가 같으면 해당 원소도 1이 더해진다. 최종적으로 모든 원소가 같아지기 위한 연산 횟수의 최솟값을 구하는 문제이다. 해당 문제는 먼저 greedy로 접근을 했었다. 최댓값을 알아내고, 결국 모든 수는 최댓값을 향하므로 최댓값 양측에 존재하는 최솟값들의 연산 횟수를 계산했었다. 1 2 3 4 ..
https://codeforces.com/contest/1921 Dashboard - Codeforces Round 920 (Div. 3) - Codeforces codeforces.com A. Square 좌표 4개가 주어지고, 해당 좌표가 만드는 사각형의 넓이를 구하는 문제이다. 주어진 문제는 축에 평행하다는 조건이 있었는데, 이를 못보고 CCW 알고리즘을 이용하여 문제를 해결했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include #include using namespace std; int main(){ int t, x, y; cin >> t; while(t--){ pairdp[4]; for(int i=0; i> x >> y; dp[i]={x,y}; } cout ..
https://codeforces.com/contest/1920 Dashboard - Codeforces Round 919 (Div. 2) - Codeforces codeforces.com A - Satisfying Constraints 입력으로 a k 가 주어졌을 때, 아래 조건을 만족하는 k의 개수 구하는 문제 1 x: k >= x 2 x: k > n; while(n--){ cin >> a >> x; if(a==1) g=max(g,x); else if(a==2) l=min(l, x); else e.push_back(x); } ans=l-g+1; for(auto p : e) if(p>=g && p> k >> x; for(int i=0; i> dp[i]; res+=dp[i]; } sort(dp, dp+n..
https://www.acmicpc.net/problem/19576 19576번: 약수 가능 한 방법 중 하나로, a2를 12로, a3을 3으로 바꾸면 된다. www.acmicpc.net 임의의 수 x, y를 잡았을 때, x%y == 0 이거나 y % x == 0이 되도록 수열 내의 원소를 바꾸어야하는데, 바꾸는 횟수가 최소가 되어야한다. 처음 접근했던 방식은 N의 범위가 1 ~ 5000이므로 반복문을 돌려 약수의 개수가 가장 많은 원소를 찾고, 해당 원소와 나누어지지 않는 원소를 바꾸는 방식이다. 그런데 코드를 돌려보니, 5 5 7 7 35 와 같은 원소가 주어졌을 때 제대로 출력이 되지 않는다는 것을 확인했고, 그래서 똑같이 반복문을 돌리되, 이번엔 약수의 개수가 아니라 나누어떨어지는 수의 개수를 구..
1. 연산자 오버로딩위와 같은 연산을 오버로딩을 통해 내가 임의로 진행할 수 있다. 예제로 살펴보자.만약 단순히 3 + 5를 진행한다면 8이라는 값을 얻을 수 있으나,(3 + 5i) + (6 + 8i)와 같이 복소수의 연산을 진행하려면 내가 생각한대로 프로그램이 돌아가지 않을 것이다.그렇기에 연산자 오버로딩을 통해 위와 같은 계산을 진행하고자 한다.123456789101112131415161718192021222324252627282930313233343536373839404142434445#include iostream>using namespace std;class Complex {private: friend Complex operator+(const Complex&, const Complex&)..