hibye1217 hibye1217

난이도: Platinum I 태그 더보기 Sweeping Segment Tree TreeSet Coordinate Compression 풀이 1. 모든 색깔을 가지지 않는 확실한 방법은? 더보기 어떤 하나의 색깔을 고의적으로 피한다면, 적어도 그 색깔을 가지지 않을 것임은 분명하니 모든 색깔을 가지지 않을 수 있습니다. 2. 특정 색깔을 가지지 않겠다고 해보자. 그럼, 가져갈 수 있는 개수의 최댓값은? 더보기 그 색깔을 가지고 있는 점의 위치를 \( (y_1, x_1), (y_2, x_2), \ldots, (y_N, x_N) \)이라고 해봅시다. 또한, \( y_1 \le y_2 \le \ldots y_N \)이라고 해봅시다. 이제 저희가 설치할 Robotic Hand의 \( y \)를 천천히 늘려나가봅..

난이도: Bronze II 태그 더보기 Parsing 풀이 1. '.'으로 나누는 것과 '/'로 나누는 것의 차이는? 더보기 두 방식의 차이는 day와 month의 순서밖에 없습니다. 이는 swap(day, month)만 해줘도 될 정도로 간단하죠. 2. 그렇다면? 더보기 일단 입력받고, '.'나 '/'로 나눠준 뒤, '.'으로 정규화를 시켜봅시다. // 이는 만약 '/'였다면 [1]을 해주면 됩니다. 그 뒤로는 '.'의 결과를 출력하고, [1]을 해준 뒤, '/'의 결과를 출력해주면 됩니다. 3. 코드 더보기 1 2 3 4 5 6 7 for _ in range(int(input())): arr = input() typ = '.' in arr; arr = list( map(int, arr.split('...

난이도: Platinum I 태그 더보기 NIM Game Bitmask Divide and Conquer 풀이 1. 1번 플레이어가 패배할 조건은? 더보기 님 게임에서 패배하는 경우는, 모든 Heap의 xor 합이 0일 때입니다. 지금 문제에서는 Heap이 N, 2N, 3N이므로, \( N \oplus 2N \oplus 3N = 0 \)인 경우겠죠. 그런데, \( 3N = N + 2N = (N \& 2N) \ll 1 + N \oplus 2N \)입니다. \( N \oplus 2N \oplus ((N \& 2N) \ll 1 + N \oplus 2N) = 0 \)을 만족하려면, \( N \& 2N = 0 \)이어야 합니다. 이는 \( N \)과 \( 2N \)에 동시에 켜진 비트가 없어야 한다는 것을 의미하..

난이도: 1609 태그 더보기 Game Theory Dynamic Programming (with Game Theory) Modular Arithmetic 풀이 1. 게임의 시작, 중간, 끝 과정을 어떻게 나타낼 수 있을까? 더보기 어차피 종료 시점에서 필요한 건 7의 배수 여부입니다. 그러므로, 중간 과정은 현재까지 계산된 수 mod 7을 가지고 있으면 되겠죠. 물론 몇 턴을 진행했는가 역시 과정에 저장하고 있어야 합니다. 그러므로, 실제 상태는 "\( (i, x) \) = \( i \)번의 턴을 진행했고, 현재 쓰인 값 mod 7은 \( x \)"로 나타낼 수 있습니다. 2. [1]에서 정의한 상태를 두고 볼 때, 그 상태에서 누가 승리하는지 알아내보자. 더보기 \( dp_{i, x} \) = 상태 ..

난이도: 1600 태그 더보기 Greedy Prefix Sum 풀이 1. 하나의 배열에서, 신경써야 하는 건? 더보기 하나의 배열에서 신경써야 하는 건 그 배열 속의 0과 1의 개수 뿐입니다. 2. 무슨 순서대로 처리해야 할까? 더보기 Exchange Argument를 생각해보면, 큰 값부터 사용해야 합니다. // 더 작은 값을 먼저 사용한다면, 그 뒤에도 작은 수가 더해져서 답이 더 작아지기 때문이죠. 3. 이 때의 답은? 더보기 이를 적용시키면, 우선 모든 1을 처리한 뒤 모든 0을 처리해야 함을 알아차릴 수 있습니다. 이제 1이 어떻게 처리되는지 봅시다. 1번째 수는 1이 됩니다. 2번째 수는 1+1 = 2가 됩니다. 3번째 수는 1+1+2 = 4가 됩니다. 4번째 수는 1+1+2+4 = 8이 됩니..

난이도: Gold I 태그 더보기 Dynamic Programming Breadth-First Search 풀이 1. 특정 Patch에서 멈추면서, 에너지를 최대로 하려면? 더보기 \( dp_{v} \) = \( v \)번 Patch에서 멈추면서, 받을 수 있는 최대 에너지 를 생각해봅시다. 저희는 Patch의 Quality가 증가하는 순서대로 이동할 것이므로, 점화식을 아래와 같이 써볼 수 있습니다. \( dp_{v} = \max\limits_{Q_w < Q_v}(0, dp_{w} - E \cdot d_{v, w}) + Q_v \) // 여기서 \( d_{v, w} \)는 \( v \)와 \( w \) 사이의 거리를 의미합니다. \( N \) 제한이 작으니, \( O(N^2) \)에 DP를 구해줄 수 ..

난이도: 1101 태그 더보기 Stack 풀이 1. 연산을 분석해보자. 더보기 문제에서 주어진 연산은 "ABC"를 "BCA"로 바꾸는 연산입니다. 이를 다르게 해석하자면, "A" 다음에 "BC"가 온다면 이 "A"를 "BC" 뒤로 미는 연산이라고 볼 수 있겠죠. 즉, "A"가 "BC"를 건너뛰어서 이동한다는 것입니다. 이 연산을 최대한 많이 하려면, "A"가 최대한 많은 "BC"를 건너뛰어야겠죠. 2. 이를 토대로, 간단히 생각해볼 수 있는 풀이는? 더보기 글자를 하나씩 읽으면서, 'A'가 나올 때마다 이 뒤에 연속적으로 있는 BC의 개수를 세주면 되죠. 다만, 주의할 점이 AAABCBC라든가, AABCABC라든가, AABCBAC라든가 다양합니다. // A 뒤에 A가 나와도 이동 가능, 심지어 BC 사이..

난이도: 459 태그 더보기 Mathematics Sorting 풀이 1. 1차원에서 생각해보자. 더보기 문제가 1차원이었다면 어떻게 풀었을까요? 가장 멀리 있는 두 점은 자명히 min과 max가 됩니다. 2번째로 가장 멀리 있는 두 점은 min이 한 칸 이동하거나 max가 한 칸 이동한 경우 중 더 먼 거리가 됩니다. 그러므로, 실질적으로 값을 비교할 때는 1, 2, N-1, N번째 값에 대해서만 비교해주면 됩니다. // 물론 여기서 i번째 값은 정렬된 후의 i번째를 의미합니다! 2. [1]의 생각을 2차원으로 확장해보자. 더보기 x축의 차이와 y축의 차이 중 더 큰 값을 가지고 온다는데, 그럼 이렇게 생각해볼 수 있습니다. [1]의 생각을 그냥 x축에 대해서 계산하고 y축에 대해서 계산한다면? x축을..