BOJ
-
[BOJ] 33980 현대모비스 V2X 자율주행 2BOJ 2025. 5. 30. 14:03
문제1번 차량과 2번 차량이 0 에서 N 까지 이동합니다. 각 차량은 매 초 R 또는 U 이동 중 하나를 합니다. 두 차량은, 2N의 이동을 하고, 문자열로 주어집니다. 이 때, 한 차량의 이동의 위치를 swap 할 수 있는 연산이 있습니다. 두 차량이 겹치지 않도록 이동경로를 구성하는 최소 연산의 횟수를 구하시오.관찰두 차량이 겹치지 않게 이동하기 위한 조건을 생각해보자. 특정 시간에서 R 개수와 L 개수가 같으면 안된다.R이랑 L 은 무조건 N 개씩 있기 때문에, R 이나 L 둘 중 하나만 고려해도 문제에서 필요한 정보를 얻을 수 있다. 또한 시작과 끝의 이동은 서로 달라야 한다. 시작에서 같은 이동을 하면 충돌해버린다. 또한, 한 차량의 시작과 끝 이동이 같으면 무조건 충돌이 일어나게 된다. 그렇..
-
-
Easy ProblemBOJ 2024. 11. 16. 15:06
일단 https://hapby9921.tistory.com/entry/BOJ-16644-Easy-Problem 이 블로그를 참고했읍니다. 일단 xhudy's sieve 랑 harmonic lemma 를 모르기 때문에 이것부터 공부를 하는게 ?? (공부완) for(int i = 1;i n; i=j+1) { j = n/(n/i); sum += ((n/i)/i) * (j-i+1); } ll rsum = 0; for(int i = 1; i n; i++) { rsum += (n/i)/i; } 아니 이 두개가 같다고 ?? 말이 안되네...n/i 의 합을 구하는데, 여기에 f(n/i)이면 n/i 대신 넣어주고, 밖에 g(i) 가 더해지면 구간합 빼서..
-
power tower 를 오일러 정리 적용하여 계산하기.BOJ 2024. 10. 29. 21:39
오일러 정리는 a^phi(m) === 1 (mod m) // (gcd(a,m) = 1일때) .. 을 사용하여, a^(T mod phi(m)) mod m = a^T mod m 으로 나타낼 수 있는거에요. 그런데 오일러 정리는 (gcd(a,m) = 1일때)만 성립하기 때문에, 일반적인 상황에 적용시키기 어려워 보입니다. https://stackoverflow.com/questions/21367824/how-to-evalute-an-exponential-tower-modulo-a-prime How to evalute an exponential tower modulo a primeI want to find a fast algorithm to evaluate an expression like the follow..
-
오일러 피(phi)함수를 거듭 연산했을 때 몇 번에 0이 되는가 ?BOJ 2024. 10. 28. 20:15
phi = [0]*1000010for i in range(1000001): phi[i] = ifor i in range(2,1000001): if(phi[i] == i): for j in range(i,1000001,i): phi[j] = phi[j] * (i-1) // iphi[1] = 0def countphi(k,cnt): if(k==0): return cnt return countphi(phi[k],cnt+1)lis =[]for i in range(1001): lis.append(countphi(i,0))print(max(lis))대충 피함수 구하는 체(sieve) 랑 재귀돌려서 리스트에 넣었다. 1~1001 까지는 최대 11번..
-
에라토스테네스의 체 구현BOJ 2024. 7. 23. 16:48
for(int i = 2; i*i 원래는 에라토스테네스의 체를 위처럼 구현했다. 불필요한 연산 같아서 위의 for 문에서 i*i 를 i 로 바꾸면 출력이 안됐다.왜 안되는지 고민하다가 백준에 넣어보니까 int overflow가 발생함을 알 수 있었다.... 그래서 long long 형으로 바꿔주니까 잘 작동한다.void sieve(int n){ vector visit(n+1,1); for(long long i = 2; i 근데 뭐가 더 효율적인지는 모르겠음 시간 초과나는 코드에 넣어도 똑같이 시간초과나고..