퀀텀 점퍼

다이아3을 찍기 위해 좀 어려운 문제를 풀었다. 풀면서 도파민 충전.. 재밌다!1월달에 병렬 이분 탐색을 공부하다 그만뒀는데 이번에 다시 도전했다. 계속 보다보니 이번엔 이해가 잘 됐다? 1396번 - 크루스칼 공https://www.acmicpc.net/problem/1396병렬 이분 탐색 입문 문제?라고 할 수 있다.$x$ 정점에서 $y$ 정점으로 가는 최소 온도를 구할 때, MST를 이용하면 간단하게 구할 수 있다.근데 $Q$개의 쿼리에 대해 모두 MST를 적용하면 시간 초과가 나기 때문에 방법을 찾아야 한다.MST를 구할 때 몇 번째 간선까지 사용할 지 정해두고 수행했을 때 정점 간 이동이 가능한 지 판단하는 결정 문제로 바꿔볼 수 있다. 이 점을 이용해서 병렬 이분 탐색을 적용하면 시간 내에 문..

문제 요약벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹는다.쿠폰에 적혀진 초밥을 무료로 하나 제공한다.1번과 2번을 수행한 모든 경우의 수에 대해 가장 많이 먹을 수 있는 초밥 종류의 수를 구한다.회전 초밥 벨트에 놓인 접시수: 8초밥의 가짓수: 30연속해서 먹는 접시의 수: 4쿠폰 번호: 30배열을 사용하고, 모듈로를 이용하여 회전하는 벨트 느낌으로 만들 수 있다. (원형 배열)Naive이중 포문을 사용해서 $k$개를 연속으로 선택하고, 초밥 가짓수를 세는 방법을 먼저 생각해볼 수 있다.int n = in.nextInt(), m = in.nextInt(), k = in.nextInt(), c = in.nextInt();int arr[] = new int[n];for (int i = 0; i ..

https://www.acmicpc.net/problem/27172솔브드 클래스 5의 골드 4문제. 일단 $N$범위 체크하고 10만인 것을 확인했다. $O(N^2)$ 브루트포스는 당연히 불가.$x$의 최댓값이 100만이었고, 비슷한 문제를 봤었기 때문에 수학 문제 그 중에서도 소수 판정. 에라토스테네스 체 냄새가 강하게 났다.흠... 어떻게 풀어야 하지... 내가 생각한게 맞나? 계속 의심이 들었고 결국 백준 태그를 까봤다.역시 내가 맡은 냄새가 맞았다.내 뇌가 더욱 강하게 에라토스테네스 체를 단순히 사용하는 쪽으로 치우쳤다. [실책]우선 플레이어들의 수를 오름차순으로 정렬한다.정렬된 수를 하나씩 확인하면서 현재 보고있는 수와 나누어 떨어지는 소수 그리고 지금 수를 소수와 나눈 수에 대해 각각 승 패를 ..

https://www.acmicpc.net/problem/17404 솔브드 CLASS 5를 미는 도중 만난 문제.약 두 달 전쯤 수업 시간에 풀다가 아이디어가 안 떠올랐었다.그러다 오늘 다시 도전. [아이디어]RGB거리 문제와 같이 $1$번 집부터 $N - 1$번째 집까지 현재 칠해야 할 집의 바로 앞 집의 색만 신경써서 채워나가고, $N$번 집을 칠할 때만 $N - 1$번 집과 $1$번 집의 색을 고려해주면 된다.근데 여기서 $1$번 집을 고려한다는 것은 $1$번 집에 어떤 색을 칠했었는지 알고 있어야 한다는 의미인데 어떻게 알 수 있을까?$dp[i][j]$ - $1$ ~ $i$번째 집까지 색을 칠하고, $i$번째 집에 색 $j$를 칠할 경우 최소 비용단순하게 RGB거리와 같이 0번 집이 있다고 가정하..

https://www.acmicpc.net/problem/30804 처음봤을 때 아이디어가 바로 생각나지 않았다. 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 이 문구에 너무 매몰되어 있어 유연한 사고를 하지 못한 것 같다. 다시 보는데 역시나 바로 떠오르진 않고 나이브한 방법밖에 생각나지 않는다..이중 포문으로 시작과 끝 잡고..근데 이 사이의 과일 종류를 어떻게 셀거냐? 이것도 나이브? 놉, 이건 누적합으로 생각해봄과일 번호가 1~9니까 $psum[index][10]$ 배열 만들어서. $psum[j][1..9]-psum[i-1][1..9]$​ for i to j 보단 for 1 to 9가 낫지 않겠어? 근데 $O(N^2)$이니까 당연한 시간초과 나겠고... ..