코딩하기 좋은날

0~N까지의 수를 K번 이용하여 N을 만드는 경우를 출력하는 문제입니다. N,K가 모두 j개의 숫자를 써서 i를 만드는 경우로 정의를 하였습니다. 숫자의 중복이 가능하므로 각 함수마다 0~N까지 숫자를 다돌려봐야 하므로 시간복잡도는 O(N^2*K) 정도가 되겠습니다. 아래는 코드입니다. #include #include #define MOD 1000000000 using namespace std; long long dp[220][220]; int N, K; long long sol(int k, int sum) { if (sum > N) return 0; if (K == k) { if (sum == N) return 1; else return 0; } long long &ret = dp[sum][k]; if..

그냥 대놓고 세그트리 문제입니다. 중간중간 값이 업데이트 되고 구간의 합을 구해야 하므로 구간의 합을 구하는 세그먼트 트리를 구현하면 끝입니다. 다음은 코드입니다. #include #include using namespace std; long long tree[300000]; long long arr[100010]; long long init(int node, int start, int end) { if (start == end) return tree[node] = arr[start]; int mid = (start + end) / 2; return tree[node] = init(node * 2, start, mid) + init(node * 2 + 1, mid + 1, end); } void upda..

세그트리를 이용하여 해결하는 문제입니다. 사탕을 넣거나 빼면서 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..