수학117 백준 2749 자바 - 피보나치 수 3 (boj 2749 java) 문제 : boj2749 일단 10^18 이므로 그냥 구하기는 절대로 불가능한 수치임을 알 수 있다 ㅋㅋㅋ. 내 경우엔 피보나치의 경우 행렬의 거듭 제곱으로 풀 수 있다는걸 이미 알고 있었으므로 공식만 찾아서 풀었다. 공식은 f(n)이 n번째 피보나치라 할 때, 아래와 같다. 이 때 거듭 제곱의 계산은, 분할 정복을 활용해서 O(logN)에 빠르게 구할 수 있다. 예를들어 A^8 = ((A^2)^2)^2 임을 활용하는 것이다. 혹시 모른다면 예전에 백준 게시판에 답글달았던 이 글을 참고하면 된다. 그보다, 다른분의 풀이도 보다보니 '피사노 주기'라는 것도 알게 되었다. 피보나치 수를 어떠한 수로 나눈 나머지는 항상 주기성을 가진다고 한다. 수의 세계는 신비로운 것 같다. 코드 : github import .. 2022. 4. 5. 백준 1072 자바 - 게임 (boj 1072 java) 문제 : boj1072 결국 n판 진행 후의 확률 차이가 1이면 n이 답이므로, 다음의 식을 구하면 풀 수 있는 문제이다. 이 때 x와 y는 이미 주어진 수치이므로 n에 대한 1차식이긴한데.. 난 수학적 지식이 딸려서 저걸 'n=~~' 형태로 변경할 수가 없었다 ㅠㅠㅠ 그러므로 좀 더 무식한 방법으로 진행했다. 직접 해보는거다 ㅋㅋ 우선 '만약 Z가 절대 변하지 않는다면 -1을 출력' 부분부터 예외처리하고 넘어가야 한다. 간단히 말해 맨 처음 확률이 99%거나 100%면 변경될 수 없다. 이 경우 -1을 출력해주면 된다. 다음으로는 간단히 100y/x를 구한 후, 해당 수치가 변경될 때 까지 n을 한땀한땀 증가시키면서 100(y+n)/(x+n)을 구해나가면 된다... 는 사실 이러면 시간초과가 난다. 생.. 2022. 4. 5. 백준 1644 자바 - 소수의 연속합 (boj 1644 java) 문제 : boj1644 소수의 연속합인걸 일단 생각 안하고 그냥 어떠한 자연수로 이루어진 배열이 있고, 연속한 배열의 부분합이 N인걸 찾는다고 생각해보자. 일단 단순히 모든 범위를 보려면 O(N^2) 이므로 통과할 수 없다. 그렇다고 DP로 풀자니 식이 잘 떠오르지 않았다. 보통 이런류의 연속합은 투포인터를 활용하면 쉽게 찾을 수 있다(원래는 통과할 방법 찾기 전에 대충 어떠한 수가 소수의 연속합으로 몇 번 정도 나오는지 궁금해서 대충 짜보고 돌린건데 통과했다 ㅋㅋ). 투포인터 전략만 잘 세우면 된다. st와 ed라는 두 포인터를 두고 [st, ed] 구간에 포함된 합을 계속 계산하고 있다고 해보자. 시작은 st와 ed 둘 다 배열의 첫번째에 둔다. 이 경우 ed가 증가(다음 칸으로 전진)되면 합이 늘어.. 2022. 4. 5. 백준 3029 자바 - 경고 (boj 3029 java) 문제 : boj3029 H시간은 H*60*60초 이다. M분은 M*60초이다. S초는 S초이다. 따라서 입력으로 주어진 hh:mm:ss 두 개는 간단히 둘 다 00:00:00부터 몇 초 후인지로 변경할 수 있다. 예를들어 다음의 예시를 보자. (예제 입력 2에서 위아래를 바꾼 예시이다.) 14:36:22 12:34:56 이 때 현재 시간인 14:36:22는 52582초, 나트륨을 던질 시간인 12:34:56은 45296초가 된다. 전자를 st, 후자를 ed라고 해보겠다. 이 때 ed-st를 한다면 기다리는 시간을 알 수 있을 것이다. ed-st = -7286이 된다. 그 말인 즉, 나트륨을 던질 시간은 하루 뒤였다는 얘기이니 (현재 시간의 다음날 12:34:56) 24시간을 더해주면 된다. 즉, ed가 .. 2022. 4. 2. 백준 24927 자바 - Is It Even? (boj 24927 java) 문제 : boj24927 ※ 2K로 나누어 떨어지는지 구하면 안되고, 2^K(2의 K승)로 나누어 떨어지는지 구해야 한다. 문제에 오류가 있다. 이걸 직접 계산해서 실제로 나누어 보려고 한다면 무려 90만1자리의 엄청난 수가 나온다 ㅋㅋ. 그러니 생각을 좀 바꿔보자. 어차피 2^K으로 나누어 떨어지는지만 확인하면 되므로, 단순히 2^K 성분만 확인하면 된다. 다른 소수는 생각할 것도 없다! 무슨말이냐면, 소인수 분해를 생각해보자. 위와 같이 어떠한 수를 소인수분해 했을 때 2가 몇개 있는지만 알면 된다. 240의 경우 2가 4개 존재한다. 3이랑 5는 상관이 없다. 2가 4개인 수를 나눌 수 있는 2^K는 K개 4이하일 때 가능하다. 즉, 주어진 x_i을 2로 나누어지지 않을 때 까지 계속 나누면서 2로.. 2022. 3. 30. 백준 3164 자바 - 패턴 (BOJ 3164 JAVA) 문제 : boj3164 우선 뭐 배열에 직접 그린 후에 직접 세는 방식은 O(X*Y) = O(10^12) 이므로 불가하다. 애초에 메모리도 엄청 많이 들 것이다. X와 Y가 최대 10^6 이므로 시간내에 풀기 위해서는 O(N)이나 O(NlogN) 급의 풀이가 필요하다. 혹시 어떻게 푸는지 감이 안왔다면 아래의 그림을 보면 바로 아! 라고 외칠 것이다. 그래프를 2개로 나눠서 보면 쉽게 풀이법을 생각해낼 수 있다. 문제에서 제시된 그래프 그대로 풀이를 찾기엔 좀 난해할 수 있지만, 아래와 같이 가로 성분과 세로 성분을 나눠서 생각해보면(세로 성분의 맨 위는 가로성분에 이미 포함된다.) 그냥 범위내에 포함되는 매번 +2씩 증가하는 기둥의 길이를 구하는 문제가 된다. 가로 기둥 최대 50만개, 세로 기둥 최대.. 2022. 3. 19. 백준 18917 자바 - 수열과 쿼리 38 (BOJ 18917 JAVA) 문제 : boj18917 제거 연산이 '항상 A에 x가 있는 쿼리만 주어진다' 라는 조건이 있으므로 상당히 간단해지는 문제이다. 애초에 뭐 가장 앞에 있는걸 제거한다는 부분도 딱히 의미가 없다. 아무튼 있는 값에 대해서만 제거가 되므로 편하게 할 수 있다. 1. 모든 원소를 더한 값 sum과 같이 변수를 하나 두고 1 x 형태의 연산이 들어올 때 더해두고, 2 x 형태의 연산이 들어올 때 빼두면 된다. 2. 모든 원소를 XOR한 값 이게 좀 어려울 수 있다. 일단 1 x 형태의 연산은 그냥 XOR을 하면 된다. ('^' 연산)2 x 형태가 문제인데, 사실 이것도 그냥 XOR을 하면 된다. 왜냐면 어떠한 수 n에 대해 n^n = 0 이다. 즉 자기 자신을 빼내는 것 역시 XOR로 동일한 수를 진행하면 되는.. 2022. 2. 20. 이전 1 ··· 9 10 11 12 다음
