나 요리학원 출신임

문제가 참 길다 이해하기가 풀기보다 더 어려운 문제다 요약하자면 내가 돌을 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..

구현하는 문제다 문제 이해를 잘못해서 한시간넘게 틀리고 난리를 쳤다 문제를 자세히 보면 거리가 d이하인 적 중에 가깝고 가장 왼쪽에있는 적이 우선순위가 높다 아마 틀리는 사람들 대부분이 이 조건을 제대로 이해 못해서 틀리겠지...! 함수별로 기능을 살펴보자 inner() => 간단하게 범위를 넘어가는지 파악하는 함수 dist() => (x,y) , (a,b) 의 거리를 구해주는 함수 attack() => 공격할 적을 고르는 함수다 가장 헷갈리는 부분이였다 내가 공격할 적을 거리기준,행기준,열기준으로 for문을 잡았다 거리가 가까운 적들 중 왼쪽행에있는 적들을 봐준다 만약 조건을 만족하는 적을 찾으면 vt에 넣고 끝! solve() => 궁수 3명을 두고 적들을 총 몇명 죽이는지 계산해주는 함수다 적들이 ..

숫자 사이의 사이클을 찾는 쉬운 문제다! 스택 개념을 사용하면 금방 풀 수 있다 진짜 스택을 써도 괜찮고 배열에 넣어도 괜찮다 먼저 숫자를 계산하고 check배열을 통해 표시해준다 그리고 스택에 계속 넣어준다 그러다가 만약 이미 나온 숫자가 또 나온다면 스택에서 그 숫자부터 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 #include #include #include #include #include using namespace std; bool arr[1000010]; int n, k; int getnum(int num) { return((n*num) % k); } int main..

bfs + union_find를 배우고 풀면서 이 문제를 풀어봤다 각 칸들을 하나의 집합이라보고 문명을 bfs를 통해 넓혀가면서 4방향으로 합쳐주면 된다 합치면서 0이였던 칸은 1로 바꿔주며 큐에 넣어준다 문명이 커지다가 문명끼리 인접해도 합쳐지기 때문에 한번씩 더 봐줬다 근데 문제는 마지막에 다 합쳐졌는지 확인하는 과정에서 완탐을 버리지못하고 하나하나 다 확인해줬다~~! 시간이 덕분에 쭉~쭉 증가했다 내일 이것좀 수정해봐야겠다 추가로 이분탐색+bfs를 통해서도 많이 해결하던데 한번 공부해봐야겠다! 소스코드 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 ..