인생발전기원

문제링크 : https://www.acmicpc.net/problem/1253#include using namespace std;typedef long long ll;int main() { ios::sync_with_stdio(false); cin.tie(NULL); int N, result = 0; cin >> N; vectorv(N); for(int i=0; i> v[i]; sort(v.begin(), v.end()); for(int i=0; i v[l]+v[r]) l++; else r--; } } cout 투 포인터를 활용한 문제이다.투 포인터 사용을 위해 우선 입력받은 값들을 정렬시키고 시작한다. 해당 문제에서..

#include #include #include using namespace std;int solution(vector diffs, vector times, long long limit) { int l = 1, r = *max_element(diffs.begin(), diffs.end()); int answer = 0; while(l level { int prev_time = (i > 0) ? times[i - 1] : 0; total += (prev_time + times[i]) * (diffs[i] - mid); } } if(total > lim..

#include #include #include using namespace std;long long solution(int k, int d) { long long answer = 0; for(long long x = 0; x d의 범위가 크기 때문에 단순 이중 반복문으로 풀면 시간초과가 나는 문제이다.어차피 좌표의 개수를 알기 위해서는 x나 y값중 하나만 알아도 되기에 x축을 고정시키고 나머지 가능한 y값의 개수를 구하는 방식을 사용한다. 먼저 계산식에 따라 x^2+y^2따라서 이는 y^2 우리는 양수 쪽 범위만 필요하고, 최대 값을 찾아서 간격을 나누면 현재 x에 대해 가능한 y 값들을 알 수 있게 된다.따라서 y = sqrt(d^2-x^2)의 값을 먼저 구해준다. 이렇게 구한 y ..

using namespace std;#include long long solution(int w,int h) { long long answer = 1; answer = (long long)w*h - (w+h) + gcd(w, h); return answer;} 문제의 예제 기준 그림을 보면 잘려진 패턴이 4개 반복된다.이는 예제의 W(8), H(12)의 최대공약수 값이다.따라서 각 잘려진 패턴의 가로 세로 길이 또한 W/최대공약수, H/최대공약수를 한 (2, 3)이다. 해당 (2, 3) 형태의 직사각형에서 잘려나간 정사각형을 살펴보면 (2+3)-1의 형태인 것을 알 수 있다.근데 해당 패턴이 4개 즉, W와 H의 최대공약수 만큼 반복되기에 일단 아래의 식을 얻을 수 있다...

#include #include using namespace std;int arr[3][3] = {{1, 1, 1}, {5, 1, 1}, {25, 5, 1}}; //다이아, 철, 돌int getIndex(string minerals){ if(minerals[0] == 'd') return 0; else if(minerals[0] == 'i') return 1; else return 2;}void dfs(vectorpicks, vectorminerals, int idx, int total, int& answer){ if(idx >= minerals.size() || (picks[0]==0 && picks[1]==0 && picks[2]==0)) //곡괭이 모두 사용 or 광물 모두 캠..

문제링크 : https://www.acmicpc.net/problem/2877#include using namespace std;typedef long long ll;int main() { ios::sync_with_stdio(false); cin.tie(NULL); int K; cin >> K; K++; //2번 노드부터 시작 vectorb, v; while(K>=1) //2진수 변환 { b.push_back(K%2); K/=2; } for(int i=b.size()-1; i>=0; i--) v.push_back(b[i]); //역순 저장 for(int i=1; i 먼저 4와 7에 대해 경우의 수를 적고 규칙을 살펴보았..

문제링크 : https://www.acmicpc.net/problem/1188#include using namespace std;typedef long long ll;int main() { ios::sync_with_stdio(false); cin.tie(NULL); int N, K; cin >> N >> K; int tmp = 0; int result = -1; for(int i=1; i= K) { int gap = tmp - stri.size(); result = stri[K-gap-1]-'0'; break; } } cout 1~N까지의 값을 모두 문자열로 변환하여 길..

문제링크 : https://www.acmicpc.net/problem/1188#include using namespace std;typedef long long ll;int main() { ios::sync_with_stdio(false); cin.tie(NULL); int N, M; cin >> N >> M; cout 최대공약수를 써야한다는 것은 알았지만, 정확히 이해가 가지 않아 시간이 소요된 문제이다. 먼저 m개를 n명에게 배분해야 하기에 소세지를 m/n을 하여 배분하면 된다.하지만 나누어 떨어지지 않는 경우는 잘라야 하는 필요성이 생긴다.따라서 gcd(N, M)을 구해 가능한 만큼 그룹을 나눠주고 시작한다.여기서 각 그룹의 인원 수는 m/gcd(N, M)이다.추..

문제링크 : https://www.acmicpc.net/problem/1405#include using namespace std;typedef long long ll;int N;double dir[4], result;bool visited[30][30];int dy[] = {1, -1, 0, 0};int dx[] = {0, 0, 1, -1};void dfs(int y, int x, int cnt, double prob){ if(cnt == N) { result += prob; return; } for(int i=0; i> N; for(int i=0; i> dir[i]; dir[i]/=100.0; } visited[14][14]=1..

문제링크 : https://www.acmicpc.net/problem/3049#include using namespace std;typedef long long ll;int N;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> N; cout 내부에 교차점이 생기는 경우는, 대각선 2개가 교차되는 순간에 생긴다.하나의 대각선의 경우 점 2개가 필요하므로, 총 점은 4개가 필요한 것을 알 수 있다.따라서 주어진 N각형에서 4개를 선택한 경우의 수를 세면된다. (NC4)

문제링크 : https://www.acmicpc.net/problem/1484#include using namespace std;typedef long long ll;int G;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> G; int s=1, e=2; bool check = false; while(s 일반 브루트포스로는 오래 걸리기에 투 포인터로 풀이가 가능한 문제이다.우리가 구하는 G는 쉽게 e*e-s*s임을 알 수 있다.따라서 해당 값을 계산한 tmp의 값이 목표 G보다 작거나 같다면 e 값을 올려 값 격차를 올려 다음 값 탐색을 이어나간다.아니라면 s 값을 올려 값의 격차를 좁혀 목표 G를 찾아나간..

문제링크 : https://www.acmicpc.net/problem/1459#include using namespace std;typedef long long ll;ll X, Y, W, S;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> X >> Y >> W >> S; ll gap = max(X,Y)-min(X,Y); //직선만 ll tmp1 = (X+Y)*W; //대각선 + 직선 ll tmp2 = min(X,Y)*S + gap*W; //대각선만 (대각선만 불가하면 마지막 직선) ll tmp3 = gap%2==0 ? (min(X, Y) + gap) * S : (min(X, Y) + g..

문제링크 : https://www.acmicpc.net/problem/1027#include using namespace std;typedef long long ll;int N;int arr[51];int cnt[51];int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> N; for(int i=0; i> arr[i]; for(int i=0; i maxV) { cnt[i]++; cnt[j]++; maxV = tmp; } } } cout 기울기를 활용한 문제다.입력받은 모든 빌..

문제링크 : https://www.acmicpc.net/problem/1105#include using namespace std;typedef long long ll;string L, R;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> L >> R; if(L.size()!=R.size()) { cout 먼저 입력을 문자열을 통해 비교가 용이하도록 해준다.만약 두 문자열의 길이가 다르다면 8의 개수가 없는 수가 무조건 발생할 수밖에 없다.따라서 이 경우 바로 0을 출력하고 종료한다. 이후로는 L 문자열 사이즈만큼 현재 문자를 비교한다.L에서 8이 존재하면 카운팅하지만, 만약 R과 다르다면 바로 종료한..

문제링크 : https://www.acmicpc.net/problem/3474#include using namespace std;typedef long long ll;int T, n, cnt;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> T; while(T--) { cnt = 0; cin >> n; for(int i=5; i 범위가 굉장히 크기에 단순 브루트포스를 통해서는 무조건 시간초과가 나는 문제이다.0의 개수를 체크하려면 2*5의 경우를 세야하는데, 팩토리얼 구조상 2가 5보다 무조건 많을 수 밖에 없다.따라서 5의 배수 개수만 세서 출력해주면 된다.