궤도

문제 풀이 메모리면에서 그닥 효율적인 코드는 아닌 것 같지만 적어본다. 할 일은 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)

문제 풀이 뭐 이런 문제가 다 있지? 재미도 뿌듯함도 없는 순수 노가다 구현 문제다. 일단 정해야하는 변수가 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. 적 이동 둘 이상의 궁수가 하나의 적을 공격할 수 있다고 하니 타겟팅만 해두고 한번에 공격해야 한다. 궁수의 공격 범위는 반지름이 d인 반원의 형태라고 볼 수 있는데, 그래서 좌, 상, 우의 순서로 탐색하다 제일 먼저 찾은 적을 공격하면 된다. https://myunji.tistory.com/378 [백준] 16236번 : 아기 상어 문제 풀이 계속해서 상어를 이동시키며 이동할 때마다 bfs를 실행해야 한다. 다행히 입력 범위가 그렇게 크지 않아 bfs를 여러번 해도 시간 초과는 발생하지 않는다. 상어가 물고기를 먹는 우선순 myunji.tistory.com 가능한 모든 후보를 찾고 정렬했던 이 문제보단..

문제 풀이 어쩌다보니 요즘 삼성 문제에 대한 풀이만 올리는 것 같은데... 구현 문제가 아니고서야 코드가 다 비슷비슷해서 굳이 올리지 않는 것이다. 일단 같은 행으로 이루어진 길은 다루기가 쉬운데 같은 열로 이루어진 길은 좀 까다롭다. 그래서 아주 간단한 방법을 썼다. 1 2 3 4 이런 지도가 있다고 하자. 이 지도를 값들을 1 2 3 4 1 3 2 4 이렇게 저장할 것이다. 그냥 길을 저장할 배열을 지도의 2배로 만들고 같은 열의 길도 같은 행의 길 처럼 저장하는 것이다. 그럼 각각의 길들을 독립적으로 다룰 수 있다. 3 2 1 1 2 3 이란 길이 있다고 하자. 맨 왼쪽(i=0)에서부터 맨 오른쪽의 직전 위치(i=4)까지 살펴볼 것인데 i=0 일 때를 보자. 3->2로 내리막 경사로를 설차해야 한다..