브루트포스문제 수가 워낙 작아서 ㄹㅇ 무식하게 풀 수 있었다. www.acmicpc.net/problem/3085 3085번: 사탕 게임 첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다. www.acmicpc.net 원래는 O(N^2)에 dx dy 넣어서 판별하는거겠지만 dxdy 세그폴트안나게 잘 관리하는거도 걍 귀찮아서 x1 y1 x2 y2 뽑아놓고 둘이 바로 옆에있으면 계산하게끔 짜서 시간복잡도가 O(N^4)다.... #include char arr[51][51] = {0}; int n; int ans=0; int abs(int a){return a>0?a:a*-1;} int max(int a, int b){return a>b?a:b;} void swap(int x1,int y1, in..
통신교육 문제 겸 백준에도 있길래 날먹했다 나이스 단순한 이진탐색인데 맞왜틀을 왜이렇게 많이 했는지 모르겠고 AC받긴 했지만 솔직히 WA코드랑 뭔차인지도 잘 모르겠지만 proofed by AC기법으로 증명되었기에 여기다 써본다. www.acmicpc.net/problem/19845 19845번: 넴모넴모 2020 오래된 테트리스 게임판 위에 수수께끼의 생물 “넴모”들이 살기 시작했다. 이 게임판은 가로로 109칸, 세로로 N층 크기이고, 넴모 한 마리는 한 층의 한 칸을 차지하고 산다. 편의상 왼쪽에서부 www.acmicpc.net search 함수는 전형적인 이분탐색 함수이다. 그냥 적당히 짰다. nemo는 혹시몰라 엄청 넉넉하게 만들어뒀는데 솔직히 필요없을거같다 #include #include usi..
킹격자 갓라기 솔직히 이게 어떻게 플래3일수가 있는거지 ㅠㅠ 환형으로 입력이 주어지는데 케이스를 4가지로 나눠 생각하면 일단 입력을 2차원으로 만들 수 있다. ( 위의 사진 기준 ) 1. 그 어느것도 서로 이어지지 않음. 2. 16번과 9번이 연결 3. 8번과 1번이 서로 연결 4. 16&9, 8&1이 서로 연결 이렇게 네번 계산해서 최솟값을 구해주면 되고, 이제 진짜인 DP파트다 일단 이게 디피라는건 알았으니, 디피를 해보고자 하는데 원래는 디피테이블을 dp[i][j]는 (i,j)를 출동시킬때 라고 생각하였으나 너무 복잡해 수정했다. 디피용 배열을 세개를 만드는데, inner[k] 는 안쪽 k번이 튀어나와있는 형태로 특수소대가 배치되어있는 경우, outer[k] 는 바깥쪽 k번이 튀어나와있는 형태로 특..
소수판별 문제의 살짝 심화된 버전. www.acmicpc.net/problem/15711 15711번: 환상의 짝꿍 환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이 www.acmicpc.net 생각해볼수 있는 수학적 개념 / 코너케이스로는 크게 세가지정도가 있다. 1. 3 이하의 수가 들어오는 경우에는 절대로 소수의 합으로 표현할 수 없다. 반드시 NO를 출력해주자. 2. 4 이상의 모든 짝수는 골드바흐의 추측에 따라 두 소수의 합으로 표현할수있음이 증명된다. 3. a와 b는 int범위를 벗어난다. 반드시 longlongint를 쓰자. 모든 짝수는 그냥 YES를 출력하..
나름 괜찮다고 생각한 문제 너무 직설적이지 않으면서도 어떤 알고리즘을 써야 풀리는지가 명확해 좋았다. www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net #include #include #include #include using namespace std; queue q; int n,k; int sec=1; int visit[123456] = {0}; bool border(int pos){ if(0
www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS는 깊이 우선 탐색으로, 스택이나 재귀를 사용하여 구현할 수 있다. 나는 재귀를 사용하여 구현했다. BFS는 넓이 우선 탐색으로, 큐를 사용하여 구현할 수 있다. #include #include #include #include using namespace std; int dfsvisit[1234] = {0}; int bfsvisit[1234] = {0}; queue q..
어나더 기하 문제 https://wiki.mathnt.net/index.php?title=%EB%82%98%EB%B9%84%EC%A0%95%EB%A6%AC 나비정리 - 수학노트 현PQ의 중점 M을 잡는다. 원주위의 두 점, A, C 에서 각각 M을 지나는 선을 그어 원과 만나는 점을 B,D라 한다. 그 다음 AD와 PQ가 만나는 점을 X, CB와 PQ가 만나는 점을 Y라 하면, M은 XY의 중점이다. 나 wiki.mathnt.net 얘를 사용하면 깔끔하게 해결할 수 있다. https://www.acmicpc.net/problem/16484 16484번: 작도하자! - ① 오늘 낮에 심심해서 작도 왕인 재원이가 종이에 원 하나를 그렸다. 그 다음, 원의 임의의 현 XY를 그렸다. 현 XY의 중점을 M이..
https://www.acmicpc.net/problem/16481 16481번: 원 전문가 진우 첫째 줄에 r1, r2, r3의 값이 사이에 공백을 한 개씩 두고 차례대로 주어진다. 주어지는 모든 수는 1,000 이하의 양의 정수이다. www.acmicpc.net 이 또한 기하날먹문제 공식만 알고있다면 쉽게 풀 수 있다. 사실 이 식을 몰라서 한참 고민했다. 이 수식을 이용하면 된다. 깔끔하게 정리해주면 이 형태가 되는데 여기서 r의 값이 우리가 찾는 해이다. #include int main(){ long long int r1, r2, r3; scanf("%lld %lld %lld", &r1, &r2, &r3); printf("%.10lf", (double)(r1*r2*r3)/(r1*r2 + r2*r3..
사랑스러웠던 문제 개념 하나만 알면 날먹이 가능했다. ko.wikipedia.org/wiki/오일러_삼각형_정리 오일러 삼각형 정리 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 오일러 삼각형 정리와 그에 필요한 보조선, 보조점들 기하학에서, 오일러 삼각형 정리(Euler三角形定理, 영어: Euler's triangle theorem)는 삼각형의 외심과 내심 사이 ko.wikipedia.org 위의 오일러 삼각형 정리의 공식과 똑같이 정확히 d^2를 요구하고 있어서 그냥 저 공식에 대입만 해주면 쉽게 AC를 받을수 있었다. #include typedef long long int ll; int main(){ ll R,r; scanf("%lld %lld", &R, &r); printf..
역시 여름학교에 나온 문제 골드2인데 엄청 어렵게 풀었다 ㅋㅋ https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net #include #include #include #include #define MAX 100001 #define ll long long int using namespace std; struct PLANET{ int idx, x, y, z; }; bool cmpx (PLANET a, PLANET b){..