기술 블로그

https://www.acmicpc.net/problem/2352 LIS 문제이다. n이 40,000이나 되기 때문에, O(n^2)으로는 풀지 못 한다. 따라서, lower_bound()를 활용하여 O(nlogn)으로 풀어야 한다. 참고 : https://hsdevelopment.tistory.com/464 시간 초과 코드(O(n^2))12345678910111213141516171819202122232425262728293031323334#include using namespace std; #define Max 40001 int n, ans, dp[Max];vector v; int main(){ //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r"..

https://www.acmicpc.net/problem/17267 예전에 한참 고민하고, 고민했던 C++로 풀었던 문제이다. 그 당시에는 queue로 풀려고 하였으나, 계속 틀려서 결국 질문을 통하여 해결하였다. 최대한 자유롭게 움직여서 이동할 수 있는 최대 칸 수를 구하는 문제이므로, 최대가 되기 위해서는 상, 하로 우선 먼저 최대한 많이 움직여야 한다. 따라서, deque를 사용하여 상, 하일 때는 rear이 아닌 front쪽에 push를 해주면 된다. 물론 좌, 우일 때는 rear쪽에 push를 해준다. 또한, 내가 못 풀고 있었을 때의 코드에 대한 반례도 올려본다. 아마 deque로 말고, queue로 구현하였다면, 첫 번째 반례에서 20이 뜰 것이다.2 왼쪽에 있는 0으로 바로 가기 때문에 L..

https://www.acmicpc.net/problem/1058 dfs 풀려고 했는데, 계속 틀렸다고 나와서 플로이드-와샬, bfs로 풀었다. 내가 푼 dfs에서는 반례가 있었다. 12345676NYYNYNYNYNNNYYNYNNNNYNNNYNNNNYNNNNYNcs 위의 예시 경우0 → 1 → 2를 한 다음0 → 2 → 3을 해야하는데 이미 전에 2를 방문처리(true)로 해버려서3을 방문하지 못 한다. 따라서, 좀 더 좋은(?) dfs를 설계해야 한다. 이 부분은 나중에.. dfs(오답)123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include using namespac..

https://www.acmicpc.net/problem/1449 Greedy그리디 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include using namespace std; int N, L, ans;vector v; int main(){ //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin); cin.tie(0); scanf("%d %d", &N, &L); int pos; for (int i = 0; i

https://www.acmicpc.net/problem/18244 아래의 문제를 변형한 문제이다쉬운 계단 수 : https://www.acmicpc.net/problem/10844 dp[i][j][k] : 길이가 i이고, 끝자리가 j인 숫자. 단 k는 아래와 같다.k=1 : 2번 감소된 상태k=2 : 1번 감소된 상태k=3 : 초기 상태k=4 : 1번 증가된 상태k=5 : 2번 증가된 상태 설명은 주석으로 대체 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include using namespace s..

https://www.acmicpc.net/problem/10844 36번 째 줄을 ans += (dp[n][j] % Mod); 라고 써서, 틀렸다고 떴었다. ans을 더하면서 int 범위를 벗어나는 것 같다. dp[i][j] = 길이가 i인 수에서 j로 끝나는 쉬운 계단 수 단, 끝이 0과 9일 때만 조심하면 된다. 길이가 i이고, 끝이 0일 때는 그 전 길이(i-1)에서는 끝이 1일 때만 계단 수가 된다.길이가 i이고, 끝이 9일 때는 그 전 길이(i-1)에서는 끝이 8일 때만 계단 수가 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include using namespace std; #define Max..

https://www.acmicpc.net/problem/17615 처음 생각은 dfs를 떠올렸으나, 바로 dfs를 할 필요가 없음을 알았다.그리고 정렬도 생각했으나, 이 때에는 R, B 모두 움직이므로 불가능했다. 그래서 다시 생각을 해봤을 때 R만 움직여서 R들을 맨 왼쪽으로 옮길 것인지, 맨 오른쪽으로 옮길 것인지B만 움직여서 B들을 맨 왼쪽으로 옮길 것인지, 맨 오른쪽으로 옮길 것인지 위의 4가지 경우의 수가 있었다. 각 경우를 잘 구현하면 된다. 물론, vc의 첫 원소와 맨 마지막 원소에 따라서 잘 대처(?)해주면 된다. 코드가 길어 보이는 것은 착각일 수도 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041..

https://www.acmicpc.net/problem/17300 처음에 어떻게 접근할까 생각하다가 한 칸 건너 뛸 수 있는 상황은 16가지 상황밖에 없었다.(8가지 * 2(반대)) 예)1에서 3으로 갈 때 또는 3에서 1로 갈 때, 2를 체크해준다... 그래서 check[1][3] = check[3][1] = true로 미리 이러한 상황일 때만 가운데 숫자를 방문했는지 안 했는지 검사해준다. 또한, 1→34→67→9.. 등 이러한 경우들을 보면 가운데 점이 모두 (처음 + 끝) / 2임을 알 수 있다. 그래서 40번 째 줄에 (v[i] + v[i - 1]) / 2를 해준 것이다. i >= 1일 때로 조건을 준 것은 그 전에 어느 방향에서 왔는지 알아야 하므로, v[i - 1]을 활용하였다. 12345..