전체 글

https://www.acmicpc.net/problem/31854 문제를 요약하면,위와 같은 부등호가 주어진 경우 해당 퍼즐의 크기 조건을 만족하는 경우를 찾으면 된다. 가장 먼저 나와 인접한 값이 모두 나보다 작거나, 나보다 큰 경우를 시작 포인트로 생각해보았다.위의 예시에서는 2번, 3번, 4번, 6번, 7번, 9번 블럭이 그 예시이다.여기서 다시 모두 작은 부등호인지, 혹은 모두 큰 부등호를 고려할 것인지 선택했다. 그런데 구현하면서 살펴보니,굳이 구분할 필요 없이 나에게 조건이 달려있는 블럭에 해당하는 블럭의 위치만 따로 지정해주면 되었다. 무슨 말이냐면,우선 1행만 볼 때 1번 블럭과 2번 블럭을 비교하는 경우 1번 블럭은 2번 블럭에 의해 값이 제한된다.그러므로 1번 블럭은 2번 블럭이 채워..

p가 소수이고, gcd(a, p) = 1인 경우, a^(p-1) = 1 mod p 가 성립한다. 이를 이용하면 된다.정리는 아래와 같다. n!((n-r)!r!)^(p-2)는 거듭제곱 꼴로 재귀를 통해 구현할 수 있다. 123456789101112131415161718#include iostream>#define MOD 1000000007using namespace std;using ull=unsigned long long;ull dp[1000001];ull mul(ull x, int m){ if(!m) return 1; else if(m==1) return x; if(m%2) return x*mul(x, m-1)%MOD; ull h=mul(x, m/2)%MOD; return h..

https://www.acmicpc.net/problem/28080 Tree에서의 계산을 진행해야 한다.5 1510 2 36 -1 413 -1 5-1 -1 -1-1 -1 -1위의 입력이 주어진다면root의 value는 10이고, root의 left child의 idx는 2, root의 right child의 idx는 3이 된다.idx = 2 의 경우 parent는 root이고, value는 6이며 right child의 idx는 4가 된다.이렇게 tree가 구성이되는데, 여기서 -1의 경우 값이 지워진 노드이다.그러므로 idx==4와 idx==5의 value 값은 모르는 상태이다. 여기서 문제 조건이 반드시 left child의 value는 본인보다 작아야하며, right child의 value는 본인보..

https://www.acmicpc.net/problem/28448 문제 N개 / 난이도 K / 시간 T 가 주어진다.한 문제를 풀 때마다 광기는 K * T 만큼 쌓이고, 최대 광기는 L 만큼만 쌓여야 한다.만약 문제를 해결하면 광기는 min(KT, 5K) 만큼 사라지게 된다. 여기서 우선 알 수 있는 사실은 만약 T 즉, T  문제는 T > 5 인 경우이다. 해당 경우에는 광기가 누적되게 된다.만약 L - 현재 광기 여기서 휴식을 가장 적게 취하면서 모든 문제를 해결할 방법을 구해야 한다. 우선 누적이 되는 광기의 양을 식으로 표현하면K * (T - 5)라고 볼 수 있다. 그래서 처음 들었던 생각은 K*T가 작은 순서대로 정렬을 해야하나 싶었다.어차피 K*T + 현재 광기 > L 인 경우에는 T의 값에..

갑자기 위의 오류가 발생했다. 최근에 이런 오류도 발생했어서 이것저것 업데이트도 해줬는데 그래서 발생한 에러인 것 같다. 시작 우클릭 -> 설치된 앱 -> Micro ~~ 수정 -> 온라인 복구를 통해 재설치를 진행하니 다시 작동한다.

https://www.acmicpc.net/problem/27519 1 ~ n 까지의 정수를 소수의 합으로 표현하는 방법의 개수를 구하는 문제이다.예를 들어 8을 표현하면1) 2 + 2 + 2 + 22) 2 + 3 + 33) 3 + 5이렇게 3가지가 존재한다.여기서 중요한 점은 3 + 5와 5 + 3을 같은 방법으로 고려한다는 점이다.이는 i == 8인 경우에 dp[i] = dp[i - 3] + dp[i - 5]가 아니라는 것을 의미한다. 이를 위해서 우선 2만으로 만들 수 있는 숫자를 카운트한다.dp[0] = 1로 선언해주고dp[i] = dp[i - 2] 로 선언해주면 i == 2인 경우 dp[2] = 1을, i == 4인 경우 dp[4] == dp[2] == 1을 저장하는데,이는 곧 4를 만들기 위해..

https://www.acmicpc.net/problem/27315 24년 2학기 문제해결기법 수업 11주차 B번에 나온 문제와 유사한 문제다만 데이터가 있는 경우 구현 난이도에 관계 없이 풀 수 있다는 부분만 잘 생각해주면 된다. 우선 가장 간단한 생각은 구현 난이도 - HP(구현 능력)의 총합이 작을수록 좋은 결과이므로 구현 난이도에 따른 오름차순 정렬을 하면 좋겠다고 생각했다.다만 문제는 구현 난이도가 낮지만 아이디어가 높은 경우에는 문제를 해결할 수 없고,HD는 높지만 구현 난이도가 조금 높은 문제를 여러 문제 해결한 이후 높아진 HD에 따라 구현 난이도가 낮아진 문제를 해결할 수도 있는 가능성이 존재한다.또한, 데이터가 존재한다면 구현 난이도는 고려할 대상이 아니므로 0점을 부여해도 무방하고,에..

https://www.acmicpc.net/problem/23820 mex(S)는 S에 포함되지 않은 가장 작은 음이 아닌 정수이다.이 때 mex({ai * aj})를 구하는 문제이다. ai의 범위는 200만 이하의 음이 아닌 정수이고, 곱으로 집합의 원소를 결정하므로 절대로 나올 수 없는 가장 작은 소수는 계산해보니 2000003이다.그러므로 어떤 수를 곱하던지 상관 없이 2000003을 넘어간다면 즉시 종료하면 되고,모든 가능한 곱을 다 계산한 이후 0 ~ 2000003까지 나오지 않은 정수를 파악하면 된다.    12345678910111213141516171819202122232425262728293031#include iostream>#include vector>#include algorithm..