코딩하기 좋은날

세그트리를 이용하여 해결하는 문제입니다. 사탕을 넣거나 빼면서 update를 하고 원하는 맛의 사탕을 찾을 때는 sum을 이용하여 해당 맛이 어딨는지 찾아야 합니다. 원하는 맛을 찾을 때는 지금 구간에서 왼쪽 / 오른쪽 자식 노드를 봤을때 왼쪽 노드에 내가 원하는 순위보다 높다면 왼쪽으로 이동 하고 그렇지 않다면 현재 알아야 하는 순위에서 왼쪽 노드의 값만큼을 빼고 오른쪽으로 진행해주면 됩니다. 아래는 코드입니다. #include using namespace std; #define MAX 1000000 int tree[MAX*4+10]; int arr[MAX+1]; void update(int node, int start, int end, int diff, int index) { if (index < s..

출근 경로를 구하는 dp 문제입니다. 상근이가 동이나 북쪽으로 이동을 하는데 교차로에서 방향을 변경한 경우 그 다음번에는 방향을 변경 할 수 없습니다. 따라서 상근이의 현재 방향과 방향 전환이 가능한지 여부를 저장해 두어야 합니다. 따라서 dp 식을 dp[i][j][k][l] 로 정하고 (i,j에서 상근이는 l 방향이고 k(방향전환 가능여부) ) 의 의미를 가집니다. 따라서 이에 따라 i,j에서 총4가지 경우에 대해 아래와 같이 식을 세울 수 있습니다. 방향전환이 불가능한 경우는 이전칸에서 방향전환을 한 경우이므로 그경우를 넣어주고 방향전환이 가능한 경우는 이전칸에서 방향전환이 가능 / 불가능한 경우 모두 가능하므로 더해서 넣어줍니다. dp[i][j][0][0] = (dp[i - 1][j][0][0] +..

아기 상어가 물고기를 먹는 문제입니다. 단순 bfs 문제이긴 하지만 생각보다 이것저것 귀찮은 문제입니다. 먼저 상어는 자기보다 작은 물고기를 먹고 자신의 크기만큼 물고기를 먹으면 크기가 증가하므로 이를 저장하기 위해서 구조체를 하나 만들었습니다. 구조체에 상어의 좌표와 크기, 현재까지 먹은 물고기 수를 저장하고 bfs를 진행하여 돌리며 먹을 수 있는 가장 가까운 물고기를 찾습니다. 이때 먹을 수 있는 물고기가 여러마리라면 물고기의 좌표(x,y)가 작은 물고리를 먼저 먹어야 하므로 각 싸이클을 한번 모두돌면서 가장 좌표가 작은 물고기를 찾아서 먹어주면 되겠습니다. 이런 문제는 항상 꼼꼼하게 구현하는 것이 중요한 것 같습니다. 다음은 코드입니다. #include #include #include using n..

dp문제입니다. 처음에 계속 전구 색깔에 집착을 하여 정해진 색으로 맞출려고 했는데 잘 안되었습니다. 그런데 사실 무슨 색인지는 중요하지가 않습니다. 그냥 해당 전구의 색으로 다맞추면 상관 없기 때문입니다. dp 배열에 전구의 구간을 (왼쪽이나 오른쪽끝)의 전구색으로 바꾸는데 필요한 최소 횟수를 저장하면 됩니다. 즉 dp[i][j] = i~j 구간의 전구를 i색으로 바꾸는데 필요한 최소 횟수입니다. (저는 i로 정했습니다.) 이때 생각 해주셔야 하는 것이 전체 구간 start - end 에서 start ~ i / i+1 ~ end 구간으로 나눌 때 start 전구와 i+1 전구의 색을 비교 해야 합니다. 그 이유는 저 구간을 끝내고 돌아왔을 때 둘의 색이 다르다면 한쪽으로 색을 맞춰줘야 하기 때문에 한번..

dp 문제입니다. 각 지시사항때 두 발의 위치를 각각 인덱스로 주면 해결 할 수 있습니다. 즉 dp[i][j][k] = i지시사항때 왼발이 j 오른발이 k 라고 생각하시면 됩니다. 이후 각 함수마다 다음 지시사항을 왼발을 이용해서 진행할지 오른발을 이용해서 진행할지 처리해주시면 해결이 됩니다. 아래는 코드입니다. #include #include #include #include #define INF 987654321 using namespace std; int arr[100010]; int dp[100010][5][5]; //i번째 지시사항때 두발의 위치에 따른 사용힘 int idx; int sol(int left, int right, int cnt) { if(cnt == idx) { return 0; }..

이 문제는 공장 기계끼리 연결 했을 때 교차점을 세야 하는 문제입니다. 이게 예제 그림을 보고 또 자기가 만들어서 보면서 생각해보면 교차점이 생기는 조건을 알 수 있는데 위에 기계를 순서대로 1,2,3,4,5 ... 라고 순서를 정한뒤 아래 기계에 맞게 번호를 주게되면 예제 그림에선 아래와 같습니다. 1 2 3 4 5 2 4 1 3 5 이경우 아래 기계를 기준으로 보면 현재 나보다 앞에 있는 기계중 숫자가 큰 기계 개수만큼 교차점이 생김을 알 수 있습니다. 2 - 0개 4 - 0 개 1 - 2(앞에 2,4)개 3(앞에 4) - 1개 5 - 0개 즉 내 차례때 내 앞에 나보다 큰 수가 몇개 인지 알면 답을 찾을 수 있습니다. N end || right < start) return 0; else if (le..

dp 문제입니다. 16개 이하의 발전소가 있을 때 이발전소를 주어진 P개를 켜야 하는 문제인데 발전소의 켜짐 꺼짐 유무를 확인하기 위해 비트마스킹을 이용하여 해결을 하여야 합니다. 2^16만큼 잡아서 dp[70000] 정도로 잡아주면 되겠습니다. 이때 발전소를 키기 위해서는 켜진 발전소를 이용하여 꺼진 발전소를 키므로 각 함수에서 꺼진 발전소를 찾고 얘를 켤수 있는 발전소를 찾아서 재귀를 돌면 됩니다. 이때 cost가 0인것은 진짜로 0인 것이지 킬 수 없는게 아니라는 점(처음에 못키는줄 알았습니다.) 생각하면서 해결하면 됩니다. 외판원 순회문제와 유사한데 좀더 간단한(?) 문제 같습니다. 다음은 코드입니다. #include #include #include #include #define INF 98765..

DP 문제입니다. 이전에 풀었던 환상의 듀엣 이란 문제와 유사한데 경찰차가 이동하는 지점이 반드시 정해져 있습니다. 즉 두 경찰차는 반드시 시작지점이 아니면 사건이 발생한 어느지점에 위치하고 있기 때문에 DP 배열을 아래와 같이 정의 할 수 있습니다. DP[i][j] = 1번 경찰차가 마지막으로 해결한사건(i), 2번 경찰차가 마지막으로 해결한사건(j) 일때의 최소 이동거리 저렇게 정의한다면 우리는 max(i,j) + 1이 다음사건임을 알 수 있습니다. 이 문제는 여기서 끝이 아니라 이 최소비용을 얻었을때 각 사건을 어떤 경찰차가 해결하였는지 까지 출력을 하여야 합니다. 처음에 이 경로를 어떻게 구해야 할지 생각이 안났는데 먼저 최소 비용을 구한 후 다시 0,0 부터 시작하며 자신이 선택한 경로를 따라가..