백준30 백준 14583번 이음줄 (c++) 문제만 보고 어떻게 접으라는건지 파악하기가 힘들어서 오래걸렸다 해당 블로그에서 잘 도식화 해놓아서 참고했다. 아무튼 접힌 점 E와 F는 특정하게 몇등분된 지점이 아니므로 이분탐색해서 구해버려야 할것이다. 먼저 d의 길이는 피타고라스의 정리로 구할 수 있다.double d = sqrt(h * h + v * v); 삼각형 ABC와 ABE는 직각삼각형의 닮음 성질을 이용할 수 있는 형태이므로 h:d = a:b 라는 비례식을 구할 수 있다.해당 비례식과 a+b는 v라는 사실을 이용해 이분탐색을 진행하면 double low = 0;double high = v;while (high - low > 0.001f){ double mid = (low + high) / 2.0f; double a = mid; double b.. 2025. 2. 20. 백준 2987번 사과나무 (c++) 구해야 할것은 두가지이다1. 삼각형의 넓이 구하기 2. 주어진 좌표가 삼각형 내부에 있는지 판단 이 내용은 내가 전에 충돌 구현할때 점이 삼각형 내부로 들어왔는지 판별한 적이 있기 때문에 쉽게 풀었다. pair points[3];int n;vector> apple;double area(){ int x1 = points[0].first; int y1 = points[0].second; int x2 = points[1].first; int y2 = points[1].second; int x3 = points[2].first; int y3 = points[2].second; //|xA(yB-yC)+xB(yC-yA)+xC(yA-yB)| / 2 return (double)abs(x1 * (y2 - y3) + x2.. 2025. 2. 19. 백준 16958번 텔레포트 (c++) 노드간의 최소 거리를 전부 구해놓고 출력만 하면 편할 것이고텔레포트라는 개념도 있기 때문에 플로이드 워셜 알고리즘이 좋을 것이다. void dist(){ for (int i = 1; i 노드간의 거리를 구해준다텔레포트가 가능한 노드간의 경우 따로 처리를 해주는데, 주의할 점은텔레포트 하는 시간 t보다 노드간 직접 이동하는 시간이 짧은 경우가 있기 때문에잘 비교해주고 값을 넣는다 void calc(){ for (int k = 1; k 플로이드 워셜 알고리즘을 사용해준다. int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> t; for (int i = 1; i > s >> x >> y; city[i].. 2025. 2. 18. 백준 2022 사다리 (c++) 정보가 부족해 수학적으로는 해를 구할 수 없는 문제이지만 이분탐색이라는 폭력적인 방법으로 해를 구해버린다 비례식으로 식을 구한 후 w(두 빌딩사이의 거리)를 이분탐색으로 찾는다 핵심은 빌딩이 멀어질수록(w가 커질수록) C는 작아지고빌딩이 가까워질수록(w가 작아질수록) C는 커진다 double x, y, c;int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> x >> y >> c; double high = min(x, y); double low = 0.0f; double ans = 0; while (low+0.001f = c) { ans = w; low = w; } else { high = w; } } cout.. 2025. 2. 10. 백준 10216번 Count Circle Groups (c++) 문제를 보자마자 떠오른것이 유니온파인드였기 때문에 유니온파인드로 해결했다. int n;vector> mp;vector r;int parent[5000] = { 0, };map 자료구조를 사용했다가 시간초과를 왕창받았기에 전부 vector와 배열로 바꿨다. void init(){ mp.clear(); r.clear(); memset(parent, 0, sizeof(parent)); cin >> n; for (int i = 0; i > a >> b >> c; mp.push_back({ a,b }); r.push_back(c); parent[i] = i; }}테스트케이스의 갯수가 주어지는 귀찮은 문제이기에 init을 함수로 분리했다.parent 배열도 바로 초기화해준다. int find_parent(in.. 2025. 2. 8. 백준 21943번 연산 최대로 (c++) 상당히 복잡해보이지만 고민할 필요 없다순서도 내마음대로, 연산자는 정해진 갯수 내에서 마음대로 배치하라는 뜻은괄호따윈 의미 없다는 뜻이다.연산자 우선순위가 없고 덧셈과 곱셈만 있다는것은덧셈으로 이루어진 덩어리들을 곱해서 최대의 수를 만들라는것과 같은말이다. 완전탐색으로 수열의 어느 부분을 끊어서 나눌지 만들고곱셈의 갯수+1 만큼의 덩어리가 만들어지면수열을 순열로 만들어 모든 배치를 만들어 한번씩 계산해보아 최대값을 구한다. void sol(int idx, vector cut){ if (cut.size() == q) { calc(cut); return; } for (int i = idx; i 덩어리를 만든다.n 길이의 수열을 어느부분에서 자를지 결정한다. void calc(vector cut){ cut.. 2025. 2. 3. 백준 1443번 망가진 계산기 (c++) 8^30을 무식하게 재귀 돌리면 당연히 시간초과가 난다 곱셈은 순서가 상관없다는 점을 이용하여 가지치기를 해주자 int count10(int num){ int cnt = 0; while (num) { num /= 10; cnt += 1; } return cnt;}만들고 있는 수의 길이를 계산하기 위해 따로 함수로 빼 주었다. void sol(int current, int cnt, int idx){ if (cnt == p) { ans = max(ans, current); return; } else { for (int i = idx; i d) return; sol(current * i, cnt + 1, i); } }}2x2x2x8 과8x2x2x2는 동일하다고로 전에 곱했던 수보다 작은 수는 .. 2025. 2. 1. 백준 5577번 RBY팡! (c++) 주어지는 초기상태가 4개이상 연속된 공이 없다는 조건이 중요하다 최대 10000개의 공을 전부 3가지 색으로 바꿔가며 테스트하면 시간초과가 나지만,어짜피 위나 아래의 공과 색깔이 같은 경우에만 바뀌는 의미가 있기 때문에 2*n^2 의 경우만 탐색해주면된다솔직히 지나치게 널널한거 아닌가 싶기도 하고.. signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i > a; ball.push_back(a); } for (int i = 0; i 모든 공을 순회하며 위 아래 색으로 바꾼경우를 한번씩 테스트 해 준다. 인덱스 초과 주의 int n;vector ball;int ans = 210000000;.. 2025. 1. 31. 백준 17136번 색종이 붙이기 (c++) 풀이도 구현도 무난하게 쉬워서 골드 3정도 되는 문제 아닌가 싶었는데종료조건을 잘 생각해야 시간초과를 면할 수 있는 문제였다. vector> mp;vector paper(6, 0);int ans = 210000000;int cntOne = 0;10x10 종이의 상태를 저장할 배열각 크기의 색종이 가 몇개 쓰였는지 저장할 배열정답을 저장할 변수재귀함수 종료를 빠르게 판단 할 수 있도록 색종이 를 붙여야 할 갯수를 저장 할 변수 bool isComplete(vector> &arr){ for (int i = 0; i 만들어진 종이판이 정답으로 적합한지 판단한다.색종이 를 붙여야 할 칸이 한칸이라도 남아있으면 실패 bool isStick(vector> &arr, int x, int y, int n){ for .. 2025. 1. 24. 이전 1 2 3 4 다음
