궤도

문제 풀이 할 일을 정리해보자... 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..

문제 풀이 각 턴마다 해야하는 일을 순서대로 써보자. 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로 내리막 경사로를 설차해야 한다..