궤도

문제 풀이 각 선수가 몇 번 타자가 될 지는 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로 내리막 경사로를 설차해야 한다..

문제 풀이 이 문제의 풀이를 쓰는 이유는... 문제를 풀고 다른 사람들의 풀이가 궁금해서 블로그를 봤더니 거의 다 하드코딩(?)을 했더라 내가 짠게 엄청 좋아보이진 않지만 그래도 최대한 효율적으로 쓰려고 노력해서 올려본다. 말로 설명하기가 좀 그래서 코드를 보면서 설명하려는데 그 전에 이걸 봐두면 좋다. 내 코드에선 각 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},..