plzfday's notes

가장 단순하게는 num이 짝수와 홀수일 때를 나눠서 다르게 for문을 작성해 주면 되는데, 다른 분들의 정답을 보니 더 멋진 방식이 있어서 정리하고자 한다. total은 수열의 합으로 표현하면 \(\Sigma_{k=a}^{a+n-1}{k}=A\)이다. 어떤 a부터 시작해서 a + num - 1까지의 합을 구하면 되는 것이기 때문에 문제의 핵심은 이 a를 어떻게 구하는 지로 바뀌게 된다. 방법은 주어진 num을 써먹는 것이다. 솔직히 난 이 식을 어떻게 구했는지는 모르겠다. 하지만 전개를 통해 증명은 할 수 있으니 이걸 소개하려고 한다. a를 구하는 식은 다음과 같다: \((A-\frac{n(n+1)}{2})/n+1\). 증명의 경우 A를 a부터 a+num-1의 합 대신, (1부터 i+num-1의 합) -..

https://www.acmicpc.net/problem/12865 코드를 짰는데 중복으로 물건을 고를 수 있게 짜서 이걸 어쩌냐 하다가 그냥 포기하고 다른 분의 풀이를 봤다. 내가 다이나믹 프로그래밍이라고 하면 뭔가 생각이 점화식을 어떻게 짜는지에만 몰두하느라 생각을 우연하게 하지 못한 것이 패착인 것 같다. 나이브한 솔루션인 전체 탐색에 메모이제이션을 이용해서 시간을 줄이는 방식이라고 보면 된다. 나이브한 솔루션은 아이템 i를 뽑냐, 뽑지 않냐로 경우의 수를 나누어서 N번째 (1부터 시작했을 때) 아이템까지 확인하는 방식이다. 정말 간단하지 않은가..?? 좀 더 다양한 DP 문제를 풀면서 생각의 유연성을 길러야 할 것 같다는 반성으로 마무리하겠다.

문제 링크 입력으로 들어올 수 있는 숫자의 최댓값이 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..

문제 링크 바킹독님 강의 들으면서 예전에 풀었던 문제들도 다시 풀고 있다. 굳이 스택을 쓸 필요는 없는데 ADT의 강력함 중에 하나가 실수를 줄여주는 것 같아서 난 마음껏 썼다. 스택은 하나만 쓰면 되고 i번째 빌딩까지 갔을 때 스택에는 i-1에서 가장 큰 값만 들어있으면 된다. 그렇기 때문에 i번째 빌딩 높이가 스택 꼭대기에 있는 값보다 크면 스택를 계속 pop하면서 본인보다 큰 빌딩을 찾으면 된다. 다만 이렇게 계속 pop하다가 스택이 비는 경우가 있으니 이것만 잘 처리해주면 되는 듯하다.

문제 링크 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/1976 Union Find를 사용하면 쉽게 풀 수 있다. 만약 갈 수 있는 경로라면 find함수를 실행했을 때 반환값이 모두 같을 것이다. #include #include using namespace std; int n, m, par[201]; int find(int u) { if (u == par[u]) return u; return par[u] = find(par[u]); } void merge(int u, int v) { u = find(u), v = find(v); if (u > v) swap(u, v); par[u] = v; } int main() { scanf("%d %d", &n, &m); for (int i = 0; i