plzfday's notes

문제 링크 입력으로 들어올 수 있는 숫자의 최댓값이 10억임을 확인했지만 혹시나 싶어서 M = 2..min 까지 해봤지만 역시 틀렸었다. 근데 제출 결과가 틀렸습니다가 나온 걸 봐선 그냥 내 풀이 자체가 틀렸을 수도 있겠다. 이 문제는 위와 같은 이유로 다른 방법을 생각해야 하고 그 방법은 GCD를 활용하는 것이다. 입력이 5, 17, 23, 14, 83이면 가능한 M=3인데 입력을 다시 M과 엮어서 표현하면 5=1*3+2, 17=5*3+2, 23=7*3+2, 14=4*3+2, 83=27*3+2이다. 몫 부분을 제외하면 M과 R(나머지)은 공통되게 갖고 있는 것을 확인할 수 있다. 이 문제에서 기억해야 할 트릭은 나머지를 지우는 것이다. 예를 들어 17-5를 계산해보면 (5*3+2)-(1*3+2) = 4..

문제 링크 2018년 JOI 1번 문제다. 난로가 켜져 있는 시간은 N + α 인 것은 자명하다. 그렇다면 α를 알아야 한다. 성냥이 N보다 부족하면 계속 켜놔야 하는 시간을 알아야 하는데 예제를 보면서 계산하는 것이 좀 더 좋을 것 같다. [예시1] 1 3 6 K가 2일 땐 1 3 사이[1초]나 3 6 사이[2초]를 계속 틀어놔야 할 것이다. 이것에 착안해서 나는 우선순위 큐(오름차순 정렬)를 사용해서 (친구들 방문이 이어져 있지 않을 경우) 일 때 간격을 우선순위 큐에 저장을 시키고, 만약 이어져 있는 경우에는 cnt를 증가시켰다. 그래서 우선순위 큐에서 pop을 시키는 횟수는 가 된다. 난로가 켜져 있는 시간의 최솟값을 구해야 하므로 정답은 이 된다. #include using namespace s..

2842번: 집배원 한상덕 이분 탐색 + flood-fill도 가능하지만 inchworm 알고리즘을 사용할 수도 있다. 피로도와 방문할 수 있는 곳은 비례하기 때문이다. (찾아보니 단조함수이면 가능하다고 한다.) inchworm 알고리즘에서는 1차원으로 작업을 하는데 고차원에서도 가능한지는 모르겠다만... 아무튼 1차원에서 작업하기 때문에 2차원의 좌표에 있는 값을 1차원의 위치로 바꿔주고 정렬을 한 상태에서 inchworm 알고리즘을 돌면서 flood-fill을 했다. #include #include using namespace std; const int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, dy[] = { 1, 0, -1, -1, -1, 0, 1, 1 }; int n, ..

1309번: 동물원 지극히 개인적인 생각입니다. 제대로된 풀이는 다른 블로그 보시길 바랄게요 죄송합니다! 문제가 규칙성을 찾을 수 있을 것 같아서 야매로 찾다가 3 7 17 41이 나오길래 int n, ret = 3; scanf("%d", &n); int plus = 4, add = 6; for (int i = 1; i < n; ++i) { ret += plus, ret %= R; plus += add, add += 8; } 했지만 당연히 틀렸다. 그래서 "스티커"문제의 경험을 되살려서 대각선으로만 놓을 수 있다는 것에 착안을 했다. dp[0][i] = dp[1][i - 1] + dp[0][i - 2] + dp[1][i - 2] dp[1][i] = dp[0][i - 1] + dp[0][i - 2] + d..

1699번: 제곱수의 합 해법 DP, 동전2 문제와 굉장히 유사하다. 분명히 정올 준비를 하면서 이 문제를 풀어 봤음에도 불구하고 처음에는 n보다 작으면서 가장 가까운 제곱수를 빼주는 것으로 생각했는데 그렇게 하니까 32 = 16 + 16같은 반례에 막혔다.(당연하다... ㅠ) 그래서 다시 생각한 것이 제곱수들의 리스트가 주어질 때 i를 범위 내의 제곱수들로 뺀 수의 최소 구성 개수 중에서 가장 작은 것을 고르는 것으로 생각했다.(= min(D[i - sqrt_list[j]]) ) 그래서 나온 점화식은 다음과 같다. int Min = dp[i - sqrt_list[0]]; for (int j = 1; j 0) return dp[n]; int idx = find_close(n); dp[n] = 1 + st..

9465번: 스티커 해법 처음 내가 접근했던 방법은 그냥 무식하게 대각선으로만 생각하고 풀었다. 그래서 당연히 틀렸고 친구와 다른 분들의 도움을 받아서 이 문제를 풀게 됐다. 우선 이 문제는 DP이고 DP식은 dp[i][j]: i열,j행까지의 스티커의 최대값이다. 하나를 선택하면 상하좌우를 선택하지 못하기 때문에 기본적으로 이동은 대각선으로만 가능하다. 그래서 DP식을 대각선쪽만 생각해서 짜면 절대 안된다. 이렇게 한다면 250이 최대가 되어서 정답인 260이 아니게 된다. 즉 한 칸을 건너뛰어야 한다. 그러면 두 칸을 건너뛰는 것은 어떨까..? 결론부터 말하자면 손해다. 두 칸을 뛰게 되면 한 칸씩 대각선 건너는 것과 같은 지점을 가지만 거치는 것은 더 적으므로 항상 손해일 수 밖에 없다. 그래서 점화..

https://www.acmicpc.net/problem/1654 랜선 하나의 길이를 이분탐색하자. #include #include using namespace std; int k, n, lan[1000001], Max = -987654321; int main() { scanf("%d %d", &k, &n); for (int i = 0; i 1; int cnt = 0; for (int i = 0; i = n) ..

https://www.acmicpc.net/problem/2805 나무를 자르는 것을 이분 탐색으로 구할 수 있다. 1부터 주어진 나무의 최대 길이까지 이분 탐색을 하면서 잘라서 얻은 나무가 더 많으면 위 부분으로 조절하면 되고 반대로도 같은 방식으로 하면 된다. 하지만 그 필요한 양만큼만 못 가져갈 때도 있으므로 그럴땐 한 번 더 mid를 구한 것이 답이다. 참고: 파라매트릭 서치 #include #include using namespace std; int n, m, maxH = -987654321, tree[1000001]; int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%d", &tree[i]); maxH = ma..

https://www.acmicpc.net/problem/10815 이분 탐색 #include #include using namespace std; int n, m, ar[500001]; bool bs(int find) { int s = 0, f = n - 1; while (s find) f = mid - 1; else s = mid + 1; } return 0; } int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &ar[i]); sort(ar, ar + n); scanf("%d", &m); while (m--) { int a; scanf("%d", &a); printf("%d ", bs(a)); } return 0; }

https://www.acmicpc.net/problem/1162 벽 부수기 문제와 비슷하다. 주어만 바뀐 느낌이고 트리 구조(?)에서 그래프로 바뀐 것 뿐이다. 도로를 포장하거나 안 하거나 두 가지 경우가 있으므로 그 두 가지 경우를 모두 확인해주면 된다. #include #include #include #include #include using namespace std; struct Edg { int idx, cnt; long long dst; Edg(int idx, long long dst) : idx(idx), dst(dst) {} Edg(int idx, long long dst, int cnt) : idx(idx), dst(dst), cnt(cnt) {} bool operator nxt.dst ..