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..
PS
A - 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 ..
