https://codeforces.com/contest/1786/problem/E 문제 각각 $a_i$의 체력을 가진 $n$ 마리의 monster가 주어졌을 때, 우리는 2가지 연산을 수행할 수 있다. 임의의 살아있는 몬스터에 1의 데미지를 준다. 살아있는 모든 몬스터에게 1의 데미지를 준다. (만약, 이 과정에서 1마리 이상의 몬스터가 죽는다면, 2번 연산을 반복한다.) 2번 연산은 매 step마다 한번만 사용이 가능하다. $k = 1, 2, ..., n$ 마다, $k$ 마리의 몬스터를 모두 죽이기 위한 1번 연산의 최소 수행 횟수를 구해야 한다. example 풀이 1번 연산의 횟수를 최소로 만들기 위해선 2번 연산의 효율을 높이면 된다. (
https://codeforces.com/contest/1790/problem/E 문제 $x = a \oplus b = {a + b\over 2}$ 를 만족하는 $a, b$ 찾기 풀이 xor 연산은 두 비트가 다를 때 1이므로, $b = 0$이면 xor의 결과는 $a$의 값을 따르게 된다. 여기서 $a, b$ 에 같은 값을 더해주면 어떻게 될까? $a$와 $b$에 같은 값을 더했을 때, xor의 결과는 이전 결과와 똑같은 것을 확인할수 있다. 여기서 주의해야할 점이 하나 있는데, 같은 값을 더해줄 때 올림수가 발생하면 안된다는 것이다. 위의 결과처럼 올림수가 발생했을 때, xor의 결과가 바뀐 것을 확인할 수 있다. 이 이유를 생각해보면 올림수가 발생을 하면서 이전 xor의 결과(=a)를 담당하던 비트가 달라졌기 때문이다. 이제 문제로 돌아와서 $a \oplus b = x$를 만족하는 $a = x, b= 0$에 대해서 생각해
문제링크 : LCMSum (hardversion) 문제 $LCM(i, j, k) >= i + j + k$을 만족하는 $(i, j, k)$의 쌍의 수를 구하여라 (단, $l = i + j + k$ 인 경우의 수를 구하게 되면, $O(n^3)$의 시간이 걸린다. 따라서 전체 경우의 수 - 조건을 만족하지 않는 경우의 수를 이용하여 풀어야 한다. 전체 경우의 수 > 전체 경우의 수 $= \binom{r-l+1}3$ l, r 사이에서 숫자를 3개 뽑는 것이므로 위의 같이 구하면 된다. 조건을 만족하지 않는 경우의 수 $i$와 $j$의 값이 $nk$의 약수일 경우, $LCM(i, j, k) = nk$ 가 되기 때문에 $nk$의 값만 생각해주면 된다. 1
문제 링크 11478 서로 다른 부분 문자열 해당 문제를 substr + set을 이용하여 중복을 제거함으로써 문제를 풀 수 있다. 다만 이 방식으로 문제를 풀 경우, 호출 횟수 및 시간복잡도가 substr(500500) + set(log(500500)) 이렇게 되기 때문에 꽤나 오래 걸리게 된다. 따라서 시간을 줄이기 위한 풀이로 trie를 구현하여 풀 수도 있다. trie 구현 풀이 reference https://melonicedlatte.com/algorithm/2018/08/12/230648.html
문제 바로가기 난이도 골드2 시간제한 2초 메모리 제한 128MB 📚 해설 및 코드 ✏️ 문제 접근 문제에서의 B[k] = x는 B배열의 k번째 인덱스가 x라는 의미이다. 이를 반대로 해석하면 x 보다 작거나 같은 element의 개수는 k개라는 의미로도 해석이 가능하다. (B배열은 오름차순으로 정렬되어 있기 때문이다) 그러면 우리는 x의 값을 조정하면서(이분탐색) 문제에서 원하는 정답을 찾으면 된다. ✏️ x를 이용해 k값 찾기 ✏️ x의 후보 left : 1
문제 접근 2615번 오목 바로가기 사용 알고리즘 완전 탐색 + DFS 방향 설정 오목인지 판단을 하기 위해선 한 점에 대해서 총 8방향을 봐야한다. 하지만 2중 for문을 사용할 때, 위에서 아래 / 왼쪽에서 오른쪽으로 탐색을 하게 된다면, 파란색을 칠해진 방향에 대해선 볼 필요가 없다 (중복되기 때문) 5목 판단 DFS 시작 2중
h3, h4 {border-top: 0.25px solid #51555d54; padding-top: 16px;} `결과 : D번까지 solve(30:09) || 패널티 : 1회 ` `최종결과 - 시간 : 35:09 || Performance : 1342점 ` A - Shampoo 난이도 브론즈 분류 구현 or 시뮬레이션 사용언어 cpp 제출시도 1회 제출시간