그냥 하는 노트와 메모장

재밌는 문제라 포스팅하고자 한다. 연속된 숫자 1,5,10 이라고 한다면 심어야할 나무는 1보다 작은 위치 또는 10을 넘어가는 위치에 심을 순 없다. 따라서 1-5 간격과 5-10 간격이 다르기 때문에 각 구간에 나무를 심어야되는데, 그 간격을 정해보는 것에 포커싱을 맞춰보자. 1-5 간격은 4, 5-10 간격은 5다. 따라서 2도 3도 4,5 모두 간격으로 둘 수 없다. 따라서 1간격으로 나무를 심을 수 밖에 없다. 반면 1,5,11 이라고 가정해보자. 1-5 간격은 4, 5-11 간격은 6이 된다. 따라서 2간격만큼 나무를 심어줄 수 있다. 모든 구간에 대해 같은 간격으로 나눠져야하기 때문에 최대공약수를 이용해 구한다. 모든 간격에 대해 최대공약수를 구하면 그것을 나눈 값 - 1로 답을 구할 수 있..

BOJ 2479 - 경로찾기 문제를 먼처 푸는 것을 추천합니다. ====================================================== 해밍 경로에서 차이가 1인 것끼리 경로가 될 수 있다는 것은 문제에 나와있다. 즉, 그래프 상의 A,B 해밍코드가 연결되기 위해서는 A^B 결과의 1인 비트가 반드시 한 개여야 한다는 것이다. 그래프를 구성한 뒤, 해밍 코드 1번부터 시작하는 BFS를 구성하여 trace할 배열을 따로 설정하여 저장해주기만 하면 된다. 문제는 간선을 잇기 위한 작업인데, 가능한 서로다른 A,B 쌍에 대해 간선을 알아보기 위한 시간복잡도는 O(N^2 K)다. K를 없애고 일반 정수로 한다고 하더라도 (A^B 결과의 log2하는 등), O(N^2)라서 시간이 초과된..

우선 ax+b꼴을 예측하기 위해선 적어도 세 개의 숫자가 필요하다. 따라서 N이 1일 때와 N이 2일 때를 따로 처리해주자. 1. N = 1 무조건 답은 'A'다. 다음 숫자를 예측할 (a,b) 짝이 너무 많다. 2. N = 2 만약 두 숫자가 같다면 다음 숫자도 같은 숫자가 된다. 만약 다르다면 (a,b) 짝이 너무 많아서 'A'가 답이 된다. 3. N > 2 ax+b 꼴을 예측하기 위해 첫 세 숫자에 대해 a와 b를 fix 시킨다. 그 다음 그 fixed a,b를 가지고 모든 연속된 두 숫자에 대해 만족하는지 알아보기만 하면 된다. 수열에서 첫 숫자가 x라면 두 번째 수가 y, 다시금 두 번째 수가 x로서 feedback되므로 이 구조를 눈여겨 보자. ax+b가 모든 연속된 두 숫자에 대해 만족하기 ..

BOJ 2624 문제를 먼저 푸는 것을 추천합니다. ============================================================ 이 문제 역시 동전 바꿔주기 문제와 완전 동일하다. 단, 소수가 추가됐긴 했지만, 이는 에라스토테네스의 체로 구할 수 있다. 각 사탕에 대해서 hashing을 해줘야하며(몇 번째 사탕인지 등), 이는 map또는 vector, array 해싱으로 처리할 수 있다. 기본적인 아이디어는 캔디 종류 하나씩 처리를 해나가며 처리한다. 현재 처리해야 하는 캔디가 k번째 캔디라면 이전에 처리된 0부터 500000까지(50*10000) 가능한 가격에 대해 k번째 캔디의 가격을 더한다. 더할 때도, 같은 캔디가 여러개 있을 수 있으므로, k번째 캔디의 수가 cn..

A. Garden 바닥에 물을 흘리지 않는 -> 약수인, 최대값을 찾으면 된다. #include int main() { int n, k,d,ans=1; scanf("%d%d", &n, &k); while (n--) { scanf("%d", &d); if (!(k%d)) ans = ans > d ? ans : d; } printf("%d", k / ans); return 0; } B. Browser left, right가 존재하는 구간이 전체에 대해서 3가지 밖에 없다. 왼쪽에 몰린 경우, 오른쪽에 몰린 경우, 가운데에 있는 경우. 이 세가지 경우를 고려하여 범위 및 Greedy 접근을 하여 해결한다. #include int abs_v(int a) { return a < 0 ? -a : a; } int m..

A. Hawk eyes 모든 경우에 대해 switch~case 문으로 값을 변경해주는 것으로 구성하면 된다. 마지막엔 순회하여 위치값을 출력해준다. #include #include int main() { char S[201]; int cup[4] = { 1,0,0,2 },i; scanf("%s", S); for (i = 0; S[i]; i++) { switch (S[i]) { case 'A': std::swap(cup[0], cup[1]); break; case 'B': std::swap(cup[0], cup[2]); break; case 'C': std::swap(cup[0], cup[3]); break; case 'D': std::swap(cup[1], cup[2]); break; case 'E': ..

* Modular 모듈러 연산은 덧셈, 뺄셈, 곱셈에 대해 닫혀있다. 즉, (a+b)%m = (a%m+b%m)%m과 동일하다. 나눗셈에 대해선 닫혀있지 않으므로 유의한다. ※ 페르마의 소정리를 참고.