문제링크 : 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의 배수 개수만 세서 출력해주면 된다.
문제링크 : https://www.acmicpc.net/problem/1456#include using namespace std;typedef long long ll;ll A, B;int main() { cin >> A >> B; vector v(10000001, true); v[0] = v[1] = false; for(int i=2; i*i= A) cnt++; //범위 내 카운트 if(tmp > B/i) break; //오버플로우 방지 tmp*=i; //거듭제곱 } } cout 에라스토테네스의 체를 활용한 문제이다.문제 범위에서 B가 최대 10^14이기에 이에 루트 값을 씌운 10^7범위까지 소수를 미리 체크해준다...
문제링크 : https://www.acmicpc.net/problem/2312#include using namespace std;int N, num;int main() { cin >> N; while(N--) { mapm; cin >> num; int tmp = num; for(int i=2; i*i 1) m[tmp]++; for(auto i : m) { cout 소인수 분해를 하고, 이때 소인수의 개수를 같이 출력하는 문제이다.반복문 i=2부터 시작하여 현재 입력받은 num을 나눌 수 있을 때까지 반복하여 나눠주며 map을 활용해 사용된 개수를 카운팅한다.이를 i*i주의할점은 마지막 소인수를..
문제링크 : https://www.acmicpc.net/problem/1064#include using namespace std;struct Point { double x, y;};double distance(Point a, Point b) //거리 구하기{ double dx = a.x - b.x; double dy = a.y - b.y; return sqrt(dx * dx + dy * dy);}bool isColinear(Point a, Point b, Point c) //세 점이 일직선에 있는 지 체크{ return (b.x - a.x)*(c.y - a.y) == (b.y - a.y)*(c.x - a.x);}int main() { Point a, b, c; ci..
문제링크 : https://www.acmicpc.net/problem/17087#include using namespace std;typedef long long ll;int N, S;int arr[100001];int main() { cin >> N >> S; vectorv; for(int i=0; i> arr[i]; v.push_back(abs(arr[i]-S)); } int tmp = abs(arr[0]-S); for(auto i : v) { tmp = gcd(tmp, i); } cout 최대공약수를 활용한 문제이다.입력받은 수빈이의 위치 S와 동생 간의 거리 차이 값을 모두 구하여 따로 저장하고,이 값들의 최대공약수를 구하..
문제링크 : https://www.acmicpc.net/problem/2089#include using namespace std;typedef long long ll;int N;int main() { cin >> N; if(N==0) { cout v; while(N!=0) { if(N%-2==0) { N/=-2; v.push_back(0); } else { N = (N-1)/-2; v.push_back(1); } } reverse(v.begin(), v.end()); for(auto i : v) c..