문제일단 가장 먼저 떠오르는 방법은 문자열 슬라이싱을 통해 비교하는 방법이다.n,m = [int(input()) for _ in range(2)]s = input()cnt = 0pn = 'I'for _ in range(n): pn += 'OI'for i in range(m): if s[i]=='I': if s[i:i+2*n+1]==pn: cnt += 1print(cnt)하지만 위 코드를 제출하면 첫 번째 서브테스크밖에 통과를 하지 못하고 50점을 받게 된다. python에서 리스트 l[a:b]의 문자열 슬라이싱의 시간복잡도는 $O(b-a)$ 라고 한다. 주어지는 S가 커질수록 시간이 오래 걸릴 수밖에 없다. 그럼 문자열 슬라이싱 말고 그냥 부분 부분 잘라서 비교..

문제간단한 정수론 문제이다.$$ A^{B^C}, B^C / A$$결국 이 두개를 0.25초 안에 계산하면 되는 문제라고 볼 수 있다.첫번째의 경우에는 페르마의 소정리를 이용하면 간단하게 구할 수 있다. 페르마의 소정리는 아래과 같다. $$ p\text{가 소수이면, 모든 정수 }a\text{에 대해 } a^p\equiv a\left({\rm mod}\ p\right) \text{이다.}$$ 이는 동치인 아래의 정리로 바꿀 수 있다. $$ p\text{가 소수이면, 모든 정수 }a\text{에 대해 } a^{p-1}\equiv 1\left({\rm mod}\ p\right) \text{이다.}$$우리는 아래의 정리를 사용할 것이다. $  A^{7-1}\equiv 1\left({\rm mod}\ 7\righ..

문제중국인의 나머지 정리(CRT)를 알고 있는 사람이라면 바로 해당 정리를 이용해서 문제를 풀어야겠다는걸 알 수 있다. 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)알고리즘이나 정수론, 암호학을 공부하면 항상 등장하는 개념인 중국인의 나머지 정리에 대해 알아볼 것이다.중국인의 나머지 정리란?중국인의 나머지 정리는 다음과 같은 여러 선형 합동nivr4y.tistory.comCRT는 주어진 법들이 서로소 관계일때만 적용되므로, 일반적인 CRT와는 약간 다르게 바꿔서 함수를 짜야 한다.풀이import sysinput = sys.stdin.readlinedef ext_euc(a, b): if b==0: return a, 1, 0 g, x, y = ext_euc(b, a..

문제나의 첫 플레티넘 문제이다!! 이전 글에서 확장된 유클리드 알고리즘을 공부한것이 큰 도움이 되었다.2024.09.23 - [BOJ/이론] - Extended Euclidean Algorithm (확장된 유클리드 호제법) Extended Euclidean Algorithm (확장된 유클리드 호제법)확장된 유클리드 호제법이란?2024.07.18 - [BOJ/이론] - 유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기  유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기유클리드 호nivr4y.tistory.com문제에서 요구하는 것을 식으로 만들어 보면 다음과 같다.$$ k \cdot x + c \cdot y \equiv 1 \mod c $$이는 확장된 유클리드 알고리즘으로 ..

문제2 x 1, 1 x 2 타일로 2 x n 짜리 타일을 채우는 방법의 수를 물어보고 있다. 이 문제를 푸는 핵심은 우리가 이전에 구했던 경우의 수 들로 다음 경우의 수를 구해야 하는 것이다. 전 항과 우리가 구하려고 하는 항의 관계를 흔히 점화식이라고 부른다.다이나믹 프로그래밍 문제를 푸는 데의 핵심은 점화식을 구하는 것에 있다. n=1 부터 초반 몇 개 항을 적다 보면, 항들 간의 관계를 생각해볼 수 있는데, 우리가 2 x k 짜리 타일을 채우는 방법을 고민할때, 2 x k 타일을 채우는 경우의 수는 2가지밖에 없다. 2 x (k-1) 짜리 타일에 1 x 2 타일을 마지막에 붙이거나, 2 x (k-2) 짜리 타일에 2 x 1 타일 2개를 2 x 2로 만들어서 붙이는 것이다. 결국 2 x n 짜리 타일..

문제정수 X를 주어진 연산을 이용해 1을 만드는 방법들 중 최솟값을 구하는 방법이다. 시간 제한은 0.15초로 여유롭지 않은 것을 알 수 있다. python은 1.5초, pypy는 0.7초이다.시간 초과 코드import sysdef solve(a): if a == int(a): a = int(a) if a == 1: return 0 if L[a] != -1: return L[a] else: t = min(1+solve(a/3), 1+solve(a/2), 1+solve(a-1)) L[a] = t return t else: return 9..

문제문제에서 주어지는 두 수 N, K를 이용해 이항 계수 $ \binom{n}{r} $ 즉, $ _nC_r $ 을 구하는 문제이다.Combination의 정의인 $ _nC_r = \frac{n!}{(n-r)!r!} $ 을 이용해서 풀 수도 있겠지만, 이전에 올렸던 이항 계수의 성질을 이용하면 훨씬 빠르고 효율적으로 구할 수 있다.2024.07.20 - [BOJ/이론] - 조합(Combination)과 이항 계수를 python으로 구현해보자. 조합(Combination)과 이항 계수를 python으로 구현해보자.조합의 정의조합(Combination) : 서로 다른 n개의 원소에서 r(단, 0를 중복 없이, 순서를 고려하지 않고 선택하는 것.중요한 것은 순열과 같이 선택해서 나열하는 것이 아닌, 선택하기만 ..

문제문제에서 주어진 두 자연수를 이용해 최대공약수와 최대공약수를 출력하면 되는 간단한 문제이다.최대공약수와 최소공배수를 python으로 구하는 방법은 이전에 올렸던 글을 참고하자2024.07.18 - [BOJ/이론] - 유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기 유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기유클리드 호제법이란?호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.호제법(互除法)이라는 단어가 따로 있는것은 아니고, 서로(互) 나누기(除nivr4y.tistory.com  코드def gcd(a,b): return a if b==0 else gcd(b,a%b)def lcm(a,b): return a*b..