궤도

문제 풀이 메모리면에서 그닥 효율적인 코드는 아닌 것 같지만 적어본다. 할 일은 2개밖에 없다 1. 파이어볼 이동 2. 파이어볼 분리 파이어볼의 상태를 저장할 구조체가 필요하겠고, 한 좌표에 둘 이상의 파이어볼이 있는지도 잘 체크해야 하고... 또 사라진 파이어볼을 어떻게 처리할지도 생각해야 한다. 아 그리고 격자의 크기가 최대 50인데 속력의 크기는 최대 1,000이다. 이걸 하나하나 움직이는건 당연히 비효율적이니 모듈러 연산을 사용해야 한다. 소스코드 #include #include using namespace std; struct info { bool is_remain; int r, c, m, s, d; }; int N; vector board; vector fire; pair dir[8] = {{..

문제 풀이 최소 동작 횟수라고 했으니까 BFS로 풀면 될 것이고, 가로로 놓는 경우와 세로로 놓는 경우의 visited를 따로 처리해야하니까 3차원 배열로 visited를 처리해야겠다. 그리고 3개를 다 들고 돌아다니는건 좀 비효율적이니까...가운데에 있는 통나무 하나만 들고다니려고 한다. 왜 굳이 가운데를 쓰냐면 그게 회전할 때 편하기 때문이다. 통나무의 상태, 그리고 하려는 동작에 따라 체크해야하는 범위가 다르다. 가로 통나무를 UDLR 하면 1x3의 범위를 확인해야 하고, 세로 통나무를 UDLF 하면 3x1의 범위를 확인해야 하고, T하면 3x3의 범위를 확인해야 한다. 이걸 하나하나 따로 처리하는건 비효율적이니까 함수로 만들어서 관리하려고 한다. 소스코드 #include #include #incl..

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

문제 풀이 각 선수가 몇 번 타자가 될 지는 next_permutation으로 구하면 된다. 다만, 1번 선수가 4번 타자인건 고정이니 2~9번 선수들에 대해서만 순열을 돌리고 4번 타자가 된 선수와 1번 선수를 바꾸면 되겠다. 점수나 다음 타자는 이닝이 바뀌어도 누적되는 결과니까 전역변수로 처리하면 된다. 그리고 1, 2, 3루 각 플레이트에 선수가 있는지 없는지를 저장해야 하는데...나는 비트 마스킹을 썼다. 1110 : 1, 2, 3루에 주자 존재 0100 : 2루에 주자 존재 1010 : 1, 3루에 주자 존재 가장 오른쪽 비트는 이번에 나선 타자를 위해 남겨뒀다. 아무튼 이런식으로 하면 주자 이동도 3루타 일때 (1011)

문제 풀이 그냥 평범한 bfs로 풀 수 있을 것 같은데 생각을 하나 해야한다. 예제 입력 1을 보면 알 수 있듯이 이미 방문한 정점이지만 f 열쇠를 획득한 이후엔 다시 방문할 수 있다. 열쇠 보유 '상태'가 달라졌기 때문이다. https://myunji.tistory.com/289 [백준] 2206번 : 벽 부수고 이동하기 문제 풀이 너어무 어려웠다. 골드 4길래 풀만할 줄 알았는데 아니었다. 반례가 너무 많았어서 기억도 안나고 여기서 더 최적화 할 수 있을 것 같은데 더 이상 못하겠다. 솔직히 설명도 잘할 자신 myunji.tistory.com 이 문제랑 비슷한 개념인데, 참고로 저 문제 이제 완벽하게 이해해서 관련 문제도 2차원 배열 내에서 다 해결했다. 뿌듯 아무튼 저 문제에서의 상태는 '벽을 부순..

문제 풀이 뭐 이런 문제가 다 있지? 재미도 뿌듯함도 없는 순수 노가다 구현 문제다. 일단 정해야하는 변수가 x, y, d1, d2이니 4중 루프를 돌려야 하는데 당연히 나는 중간에서 코드를 쪼갰다. x, y를 기준으로 잡고 d1, d2를 구할 수도 있고, d1, d2를 기준으로 잡고 x, y를 구할 수도 있는데 난 후자로 했다. 그게 더 계산이 쉬울 것 같아서였다. d1과 d2의 범위는 정해진 조건을 들고 잘 계산해보면 (d1+d2)

문제 풀이 예전엔 구현 문제가 정말 싫었는데 요즘은 좀 괜찮은 것 같다. 풀고나서 성취감이 커서 그런가 싶다. 회전의 순서는 next_permutation으로 정했다. 각 연산에 대해 s개의 정사각형이 움직이게 되는데...이걸 그림으로 표현하면 이렇게 된다. 제일 큰 문제가 회전일 텐데...나는 큐를 썼다. 자세한건 코드를 보면서 설명하겠다. 소스코드 #include #include #include #include using namespace std; struct info { int idx, r, c, s; }; vector matrix; pair dir[4] = {{0, 1}, //우 {1, 0}, //하 {0, -1}, //좌 {-1, 0}}; //상 void rotate(int sr, int sc,..

문제 풀이 할게 많아보이는데 그렇게 많진 않다. 1. 두 선거구로 나눈다. 2. 두 선거구의 인구 차이를 구한다. 3. 두 선거구를 올바르게 나눴다면 인구 차이의 최솟값을 갱신한다. 2번과 3번의 순서가 바뀌어야 하지 않나?라고 생각할 수도 있다. 근데 인구 차이를 먼저 구하고 그 값이 현재의 최솟값보다 크거나 같다면 3번을 실행하지 않을 것이다. 그럼 불필요한 연산을 하지 않으니 시간이 좀 줄어들 것이다. 두 선거구를 나누는 조합 연산은 비트마스킹으로 했다. 소스코드 #include #include using namespace std; vector split, visited; vector population; vector graph; int calcDiff() { //두 선거구의 인구 차이 int bl..