궤도

문제 풀이 할 일을 정리해보자... 1. 상어가 위치한 곳에 있는 물고기를 먹음 1.1 상어의 위치, 방향 정보 갱신 1.2 물고기 삭제 처리 1.3 상어의 새로운 위치를 공간에 기록 2. 1~16번 물고기 이동(아직 살아있는 물고기만) 3. 상어가 이동할 수 있는 모든 공간 탐색(백트래킹 재귀 함수) 3.1 상어가 더 이상 이동할 수 없으면 최댓값 갱신 공간의 현재 상태를 기록할 4x4 2차원 배열과 상어+물고기의 위치, 방향 정보를 기록할 1차원 배열이 필요하다. 상어는 여러 칸을 이동할 수 있지만 방향을 바꿀 수 없고, 물고기는 한 칸만 이동할 수 있지만 방향을 바꿀 수 있다는 차이점을 염두해야 한다. 소스코드 #include #include using namespace std; struct inf..

문제 풀이 이 문제의 풀이를 쓰는 이유는... 문제를 풀고 다른 사람들의 풀이가 궁금해서 블로그를 봤더니 거의 다 하드코딩(?)을 했더라 내가 짠게 엄청 좋아보이진 않지만 그래도 최대한 효율적으로 쓰려고 노력해서 올려본다. 말로 설명하기가 좀 그래서 코드를 보면서 설명하려는데 그 전에 이걸 봐두면 좋다. 내 코드에선 각 cctv의 범위가 이렇게 세트로 묶여 있다. 무슨 말인지는 코드를 보면 이해될 것이다. 소스코드 #include #include #include using namespace std; typedef pair pp; int N, M, result = 65; vector board; vector cctv; //cctv 위치 pp direction[4] = {{-1, 0}, //상 {0, 1},..

문제 풀이 비트마스크로도 풀 수 있다는데 난 백트래킹으로 풀었다. 근데 bfs로도 풀 수 있나보다. 먼저 상하좌우에 대해 각 구슬의 새로운 위치를 찾는다. 직전에 갔던 방향으로 또 이동할 필요는 없으니 그 방향은 제외한다. 두 구슬의 위치변화가 없거나 파란구슬이 빠진 경우는 제외한다. 만약 두 구슬의 새로운 위치가 같다면 같은 칸에 구슬이 2개 있을 수는 없으니 원래의 선후관계를 따져 구슬을 이동한다. 이동 횟수가 10을 넘어가거나 현재의 최솟값을 넘어가면 더이상 탐색하지 않는다. 소스코드 #include #include #include #include using namespace std; typedef pair pp; int result = 11; vector board; pp dir[4] = {{-1..

문제 풀이 일단 주어진 도미노의 총 개수는 36개이므로 이 도미노들의 정보와 사용여부를 map으로 관리하기로 했다. 그리고 빈 공간을 발견할 때마다 가로 또는 세로로 배치할 수 있는 도미노를 찾아보는데 1 1 1 상하좌우로 배치할 필요없이 그냥 2개의 방향만 고려하면 된다. 위 또는 왼쪽으로 배치하는건 이전 경우에서 고려됐을 것이기 때문이다. 아무튼 그래도 하나의 위치에 대해 최대 4개의 경우를 고려해야 한다. (가로세로)*(도미노 방향 2) 하나의 도미노에 적힌 숫자는 다르기 때문에 해당 위치에 이 도미노가 들어갈 수 있을지 확인할 때 도미노를 쪼개서 각각 고려해도 문제가 없다. https://myunji.tistory.com/202 [백준] 2580번 : 스도쿠 문제 풀이 입력을 어떻게 처리하여 어떤..

문제 풀이 문제가 참 긴데 사실 마지막 문단을 빼곤 쓸데없는 말이다. 입력값 처리의 벽만 넘으면 아주 못 풀 문제는 아니다. 일단 한줄로 들어온 저 input을 예쁘게 정리하면 - + 0 + + + + - - + 이렇게 된다. S[i][j] = A[i]+A[i+1]+...+A[j]라고 했다. 그럼 S[0][0] = A[i]인 것이고 S[i][i]에는 A[i]의 부호가 있는 것이다. 나름 괜찮은 정보인데 다 풀고보니 난 이 정보를 사용하지 않았다. A[0]부터 A[3]까지의 순서로 값을 구할 것이다. A[0]은 A[0]0, A[1]>0이어야 한다. (0, 1), (1, 1) A[2]은 여기에 또 추가로 A[0]+A[1]+A[2]=0, A[1]+A[2]>0, A[2]> input; int pos = 0; f..

문제 풀이 0~9까지의 숫자를 1번씩만 쓸 수 있기 때문에 visited로 관리할 수 있다. 부등호에 따라 숫자를 넣으며 백트래킹하면 되는데 나중에 stoi를 쓰기 위해 string 변수에 답을 쌓아놓는다. 소스코드 #include #include #include #include using namespace std; vector sign; bool visited[10]; int k; long long min_num = 9876543211, max_num = 0; void backtracking(int pos, string str) { if (pos == k) { //부등호 다 쓰면 최대 최소 갱신 long long result = stol(str); min_num = min(min_num, result)..

문제 풀이 이 문제 덕분에 가끔은 정말 무식한 방법이 통할 때도 있단 것을 깨달았다. 원하는 채널로 가는 방법은 2가지가 있다. 1. +-버튼을 계속 누르기 2. 채널번호 입력후 +-버튼 누르기 일단 1번은 간단하다. 목표 채널과 현재 채널의 차이의 절댓값을 구하면 된다. 그리고 2번이 중요한데 난 가능한 모든 채널을 백트래킹으로 탐색해 최솟값을 갱신하려 했다. void backtracking(int pos, int digit) { if (digit == 0) //1 1 1 => 2 return; if (pos == digit) { int mul = 1, ch = 0; for (int i = 0; i < pos; i++) { int num = channel.back(); ch += (num * mul);..

문제 풀이 예제 입력 2에 대해 그냥 중복 상관없이 모든 수열을 사전순으로 출력하면 1 7 1 9 1 9 7 1 7 9 7 9 9 1 9 7 9 9 9 1 9 7 9 9 가 될 것이다. 여기서 중복을 제거해야 하는데 처음엔 아무리 머리를 굴려봐도 비효율적인 방법만 떠올랐다. 출력한 수열을 모두 저장해서 비교한다거나...각 숫자의 등장횟수를 세서 계산한다거나... 그러다가 백트래킹 과정을 그림으로 그려봐야겠다 싶었다. 현재 1을 선택한 상황에서 백트래킹으로 7을 선택했다. (1-7) 그리고 더 이상 고를 필요가 없으니 다시 1로 올라와서 9로 내려간다. 9가 선택된 상태이다. (1-9) 또다시 1로 올라와서 9를 선택하려고 보니 이전에 선택한 값과 같은 값이다. 이러면 탐색을 하지 않는 것이다. 9 1 9..