브루트포스문제 수가 워낙 작아서 ㄹㅇ 무식하게 풀 수 있었다. 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..