나 요리학원 출신임

수학 + 큐 문제다 시물레이션으로 풀 수 있는데 숫자 범위가 int다 최악의 경우에 21억이 8개들어오면 대충 7억번? 돌아야한다고 생각하는데 그냥 풀어도 시간안에 들어오나보다 최악의 테케가 없는건지 아니면 내가 잘못생각한거지..! 어쨌든 문제는 5바퀴를돌면 총 15씩 전체적으로 감소시킬 수 있다 그럼 우리가 감소시킬 수 있는만큼 15*k만큼 감소시키자 그리고 시물을 돌리면 편하게 답이 나온다 직접 큐를 사용하지는 않는다 그냥 q의 top이 있다고 생각하고 top을 옮기는게 더 편하다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import java.io.FileInputStream; imp..

총 N개의 입력이 들어오고 매번 입력마다 중간값을 출력하는 문제다 N이 최대 10만이기 때문에 N^2은 불가능하다! 자료구조 힙을 사용하면 된다 중간만 보기때문에 중간을 기준으로 양쪽을 힙으로 잘랐다고 생각하자 계속 첫번째 힙에 숫자를 넣어주고 만약 짝수번째 순서면 두번째 힙으로 넘겨주자 그리고 처리할게 하나 있는데 첫번째힙의 탑과 두번째 힙의 탑을 비교해서 첫번째 힙에 작은수가 들어갈 수 있게 해야한다 그럼 첫번째 힙의 top이 계속 답이된다! 참고로 첫번째는 max힙, 두번째는 min힙이다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include #include #include using namespace st..

수학문제다 가성비 좋아하는 사람을 맞출 수 있는 문제다 굿 우선 최소라는 말에 집중을 하자 처음보면 세번째 예제가 왜 저가격이 나오는지 이해가 안될수있다 하지만 생각해보면 양념 후라이드 따로사는거보다 저기서는 반반치킨을 200000 사는게 이득이다 결국 X,Y개중에 적은개수만큼은 (양념,후라이드)개를 살지 (반반*2)개를 살지 정하고 남은 숫자들 중에서도 양념따로 후라이드 따로사는것과 반반*2로사는걸 비교해보면 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include #include using namespace std; #define ll long long ll A,B,C,X,Y; int main(){ scanf(" %lld %lld %lld %lld %lld",&A,&..

문제가 참 길다 이해하기가 풀기보다 더 어려운 문제다 요약하자면 내가 돌을 2개 둘 때 상대 돌을 최대 몇개 잡아먹을 수 있냐다 상대 돌을 잡아먹는다는건 상대돌주변에 1 or 범위밖으로 구성되면된다 빈틈없이! 2개만 두기때문에 쉬운문제로 변해버린다 그냥 2중 for문으로 두곳정하면된다! 이 때 배열을 1차원으로 보자 편하게 최대 n*m으로 배열을 둔 다음에는 더 쉽다 그냥 dfs 돌려보면 된다! 끝! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59..

BFS를 이용하는 문제다!! 최적화문제!! 먼저 규칙을 찾기위해 층이 있는 트리라고 생각해보자 그럼 홀수,짝수 깊이에 갈 수 있는 곳들이 계산된다 근데 이 때 중요한 규칙이 발견된다 내가 홀수에서 방문한 곳은 다음 홀수에도 갈수있고 짝수도 마찬가지다! 이걸 발견했으면 BFS로 check배열을 check[size][2]로 잡고 홀짝에 방문하는지 확인하면 된다 나는 발견하고 참 어렵게 생각하고 계속 틀렸다 홀 짝에 반복되는 성질로 줄이지 못하고 구간이라고 생각했다 현재깊이 -2 층에서 간건 현재도 방문 할 수 있기 때문에 구간이 넓어지는걸로 풀려다가 망해따 +1, -1이 반복 된다는건 갔다가 왔다가 하므로 홀짝의 성질을 이용해야하는데 최적화의길이란.. 이런걸 생각 못하면 계속 틀리는문제는 매번 틀릴거같다....

나의 위치가 S고 Ai의 위치로 갈 수 있는 최대의 D를 구하는 문제다 그럼 처음 입력 받으면서 Ai들과 S의 입력 차를 넣어두고 최대공약수를 구하면 된다 최대 공약수를 구하는건 그냥 N으로 찾을 수 있는데 이걸 이분탐색으로 하고 정렬해서 풀고 하다가 계속 틀렸다 그냥 쉽게 N번 보면되는걸...! 어쨌뜬 모든 거리의 차는 x*D의 형태로 나오고 최대공약수 D를 찾으면 되므로 gcd를 사용하자! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include #include #include using namespace std; int n,s,ans; vector vt; int gcd(int x,int y){ if..

완전탐색 문제다 처음에 최대 8!인 순열이라고 생각해서 예제가 안나왔다 근데 계란을 칠 때는 순서는 필요 없다 따라서 최대 8^7의 시간을 갖게 되는것 같다 대충 2^21? 우선 어떤 계란을 칠지 배열에 넣어주고 그대로 한번 계산해보면 답은 잘 나온다! 계란 순서를 정하고 solve함수를 돌려서 시간이 좀 느린데 가지치기를 통해 한번에하면 좀 빠르다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include #include using namespace std; int n,ans; int order[11]; pair arr[11]; pair tem..

문제 그림보고 솔직히 쫄았따 근데 사실 어려운 문제는 아니다 그냥 입력받는것만 주의하고 문제만 잘 읽으면 바로 풀 수 있다 여기서 서로 다른걸 내서 이겨야하므로 그냥 N! 만큼 보면된다 최대 9!이다! 나머지 두명은 순서를 주니까 말 그대로 구현하면 바로 답이 나온다 물론 나는 두명을 20까지 입력받아야하는데 n까지 입력받아서 30분간 슬픈짓했다 역시 고수가 되는건 어렵나..! 먼저 각각의 순서를 order에 차례대로 지우 경희 민호 0,1,2 로 넣어준다 지우는 1~N 까지 내기위해 배열에 넣어준다 그리고 game이라는 함수를 통해 게임을 시켜주면 된다 a,b 두명이 게임을 하면 처음 준 비교표를 통해 승자를 구할 수 있다 그리고 나머지 한명은 3-a-b다 왜냐면 셋의 합이 무조건 3이 나와야하므로 그..

DP + 그래프 사이클 체크를 통해 풀 수 있는 문제다! 처음에 dp가 생각났지만 굳이 dp를 써야하나? 라는 생각으로 실패의 길로 빠져들어갔다 먼저 bfs+set을 통해 차근차근 넣어주고 지나간 정점은 set으로 확인해서 실패~ => 1->2를 갈 때와 3->2를 갈때 둘다 2에가서 사이클로 체크됨 ㅠㅠ 그리고 착하게 dfs로 그래프 그려가고 방문한점을 다시 방문하면 사이클 확인은 시간초과~ => 정점 n*m개에서 4개의 행동을 할 수 있어서 4^n*m인 것 같다! 결국 여기서 dp로 d[x][y] (x,y)에서 갈 수 있는 최대 수 를 찾아가며 cycle을 동시에 찾으면 된다! dp를 짜는건 기본 dp문제와 똑같이 짜면 된다! 예외는 없다 범위를 넘어가거나 H라면 안가고 그게 아니라면 +1하며 다음칸..

dp로 쉽게 풀 수 있는 문제다 물론 틀렸음~~~! 조건에 맞게 d[x][y][k]로 (x,y)에서 k로 놓는 방법의 수라고 생각해보자 0은 가로 / 1은 대각선 / 2 는 세로다 그럼 내가 가로로 놓기 위해서는 - 현재칸이 0이여야하고 - 다음 칸이 비어있어야하고 - 이전에 가로 or 대각 으로 놓았을 때만 가로로 놓기 가능 따라서 다음 칸이 비어있다면 d[x][y][0] += (d[x][y-1][0] + d[x-1][y-1][1])이 완성된다! 이런 식으로 3방향을 다 보면 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include #include using namespace s..