상위 99.99%의 PS

잘해지고 싶다 BOJ 24618 - Robot Instructions (P4) 더보기 N

이걸 밀고싶었는데, 너무 어려워서 결국 포기했다.. BOJ 18184 - 분할하기 (P4) 더보기 가장 높은 곳에서 켜진 비트가 k번째에서 켜졌다고 하면, 이러한 수는 \(2^{k-1}\)개 존재한다. 또한 모든 수는 2의 거듭제곱의 합으로 나타낼 수 있으므로, 답은 항상 존재한다. BOJ 18193 - 비행기 타고 가요 (D4) 더보기 구간 간선 테크닉 + 다익스트라. https://www.acmicpc.net/problem/25392 BOJ 18194 - Bad Hair Day와 기댓값 (P1) 더보기 \(i\)번째 소보다 작은 소가 \(k\)마리라면, 이들보다 큰 소들 \((n-k)\)마리를 먼저 세워볼 수 있다. 여기서 사이사이에, 즉 \((n - k + 1)\)칸에 소 \(k\)마리를 잘 배정할..

최근들어 제대로 된 PS를 하기로 했다. 그냥 무지성으로 웰논 골플 문제를 푸는 것이 아닌, 깊은 생각을 요하는 문제를 풀어야겠다... BOJ 18287 - 체스판 이동 (P2) 더보기 행렬식 dp문제다. 홀수 행렬과 짝수 행렬을 곱해준 행렬을 N제곱하면, 2N번 이동했을 떄의 경우의 수가 된다. 여기에서 \(2k+1\)꼴로 이동하기 위해서는, k제곱한 행렬에 홀수 행렬을 곱해주면 된다. BOJ 24894 - 내적 (P1) 더보기 식을 잘 건드리면 \(\frac{y_i}{x_i}\)에 대한 cht를 할 수 있다. BOJ 10847 - 자카르타의 마천루 (D4) 더보기 그냥 다익스트라 돌리면 된다. 다만 b+kp (k는 자연수)에 동일한 p값을 가진 도게가 있다면 이보다 더 큰 b + (k+1)p부터는 볼..

21, 22일은 여행 이슈 BOJ 25488 - 토큰 (P4) 더보기 scc에 속하는 토큰의 개수가 같은 채로 유지되어야 문제의 조건을 만족한다. BOJ 23268 - Deceptive Directions (G2) 더보기 일단 bfs로 가능한 보물의 위치는 주어진 문자열을 통해서 대충 구해놓을 수 있다. 그러나, 경로는 무조건 최단경로여야 하므로 각 셀의 거리를 전처리하면 된다. BOJ 17625 - 고압선 (D2) 더보기 점 a, b, c에서 선분 ab와 점 c의 거리, 또는 어떤 두 점 사이의 거리 중 최대/2를 구해야 하는데, 어떤 두 점을 잇는 선분에서, 이와 수직인 선분을 지나는 다른 점은 존재해서는 안 된다. 이는 한 점을 90도를 돌리면 된다. 이거를 불도저로 구하면 끝이다. BOJ 1649..

개강 전까지 1000솔 찍기라는 목표를 달성했다. 하지만 실력은 오르지 않는 기분이다. BOJ 8188 - Intelligence Test (G1) 더보기 수열 b의 첫 번째 윈소부터, A에서 찾아주면 된다. 가장 왼쪽에서 채워야 하니 각 수마다 인덱스 배열을 만들어줘서 이를 찾아주면 된다. BOJ 2988 - 아보가드로 (P2) 더보기 한 쪽을 고정하고, 다른 두 배열에서 사라지는 수들을 다시 고정된 배열에서 확인하며 지워나가는 방식으로 풀면 된다. bfs 느낌..? BOJ 8221 - Letters (P5) 더보기 inversion의 개수를 세는 문제이다. BOJ 2162 - 선분 그룹 (G1) 더보기 선분 교차 + DSU로 풀린다. 마지막에 부모 압축을 해주어야 함에 유의. BOJ 3648 - 아이..

BOJ 9007 - 카누 선수 (G3) 더보기 MITM 기초문제이다. BOJ 9010 - Möbius Strip (G3) 더보기 가로와 세로를 따로 계산할 수 있다. 식 정리는 매우 깔끔하게 나온다. BOJ 9011 - 순서 (G5) 더보기 R_n부터 거꾸로 돌아가며 배열을 채워주면 된다. N이 작아서 가능함 BOJ 22348 - 헬기 착륙장 (P4) 더보기 dp[r][a] = 반지름이 r이고 어떤 색의 페인트를 a만큼 사용했을 때의 경우의 수로 정의하자. 이 dp의 누적합을 또 만들어 주고 각 쿼리를 O(1)에 구하면 된다. BOJ 1071 - 소트 (P5) 더보기 문제가 하라는 대로 O(N^2)로 풀면 된다. 단순 구현 BOJ 2320 - 끝말잇기 (G1) 더보기 dp[l][r][bit] = 왼쪽과 ..

BOJ 10883 - 분할 (P3) 더보기 행과 열 각각에 대하여 bfs를 돌려주자. 각 단계마다 1*K꼴의 사각형이 존재하는지 확인하고, (1의 개수)*(K의 개수)를 ans에 더해주면 된다. 각 분할의 단계마다 상태는 최대 2가지 존재할 수 있어서 터질 걱정은 안 해도 된다. BOJ 22984 - 반짝반짝 2 (G5) 더보기 기댓값의 선형성. 일단 사이에 추가된 전구를 무시하는 경우는 단순히 \(p_i\)를 다 더하면 되고, 추가된 전구가 켜질 확률은, 이웃한 두 전구 중 하나만 켜질 확률과 같다. 이 확률을 \(sum(P)\)에 더해주면 된다. BOJ 4354 - 문자열 제곱 (P5) 더보기 kmp의 실패함수를 이용하자. fail[s-1]이 \(\frac{ s(k-1) }{ k }\) 꼴이어야 한다..

kmp 공부 해야되는데.. BOJ 19586 - 울타리 (D5) 더보기 2차원 평면의 점에서 가장 거리가 먼 두 점은, Rotating Calipers를 이용하여 구할 수 있다. 이를 응용해서 90도와 270도 방향의 직선을 찾을 수 있다. 벡터의 내적과 외적을 이용하면 된다. BOJ 11000 - 강의실 배정 (G5) 더보기 스위핑?처럼 풀 수 있다. 구간 \([l, r]\)에서 \(l\)에는 +1, \(r\)에는 -1을 해주고, 쭉 훑으면서 최댓값을 찾으면 된다. BOJ 25392 - 사건의 지평선 (D4) 더보기 \(a_i\)가 담당하고 있는 구간 \([l, r]\)에 속하는 수들에 간선을 쭉 보내주자. 어느 순간부터 수가 일정하게 반복된다는 것은, 어떤 정점이 간선을 타고 가다가 scc에 들어가는..

어제는 ucpc, 오늘은 icpc 팀연습을 했다. 힘들다. 심지어 오늘은 몸살 기운 때문에 컨디션이 너무 안 좋아서 팀연습 때 트롤을 했다.. BOJ 20191 - 줄임말 (G2) 더보기 문자열의 i번째 글자의 위치를 이분 탐색으로 찾아주면 된다. BOJ 3654 - L퍼즐 (D5) 더보기 어떤 B에 대해, 상하를 true/false로 두고, 좌우를 true/false로 두자. 그리고 B와 연결된 W에 대해, 이 W와 연결된 B에 대해서도 논리식을 세워주면 된다. 나는 2-sat을 연습하기 위해 이렇게 풀었는데, 단순 bfs로도 풀린다고 한다. BOJ 14961 - Untangling Chain (P5) 더보기 i번째에, (i-1)번째와 동일한 방향으로 회전하는 경우라면 i칸을 이동하고, 아니라면 1칸을..

골랜디. BOJ 22345 - 누적 거리 (G2) 더보기 배열을 좌표 기준으로 정렬하고, 각 쿼리마다 이분 탐색을 통해 인덱스를 찾으면 된다. 누적 합을 사용해야 안 터짐 BOJ 16207 - 직사각형 (G2) 더보기 두 개씩 짝을 지을 수 있는 막대들을 긴 것부터 사각형을 만들면 된다. BOJ 14941 - 호기심 (G2) 더보기 홀수 짝수 인덱스 누적 합 배열을 각각 만들어 주고, upper_bound로 소수 배열의 인덱스 구간\(l\), \(r\)을 찾을 수 있다. BOJ 2464 - 비밀번호 (G2) 더보기 코포 1A로 잘 나올 것처럼 생긴 문제다. 작은 수는, 가장 오른쪽의 '10'을 찾아서 '01'로 바꾼 다음, 이 뒤쪽에 나오는 1들을 왼쪽으로 싹 몰아주면 된다. 큰 수는 반대로 하면 된다...