hibye1217 hibye1217

난이도: Platinum IV 태그 더보기 Dynamic Programming → Expected Value Probability Theory 풀이 1. 2번 더 나와야 하는 수가 \( a \)개 있고, 1번 더 나와야 하는 수가 \( b \)개 있을 때의 기댓값은? 더보기 \( dp_{a, b} \) = 2번 더 나와야 하는 수가 \( a \)개 있고, 1번 더 나와야 하는 수가 \( b \)개 있을 때의 기댓값 을 정의해봅시다. 초항은 \( dp_{0, 0} = 0 \)입니다. 점화식은, 랜덤한 수를 뽑았을 때 나올 수 있는 3가지 경우로 나눠봅시다. 2번 더 나와야 하는 \( a \)개 중 하나일 때: \( dp_{a-1, b+1} + 1 \) 1번 더 나와야 하는 \( b \)개 중 하나일 때: ..

난이도: Gold III 태그 더보기 Dynamic Programming 풀이 1. \( N \)개의 곡을, 각자 \( a, b, c \)개씩 부르는 경우의 수는? 더보기 \( dp_{N, a, b, c} \) = \( N \)개의 곡을 각자 \( a, b, c \)개씩 부르는 경우의 수 라고 해봅시다. 초항은 \( dp_{0, 0, 0, 0} = 1 \)이 됩니다. 점화식은, 3명 중 1명 이상이 부르는 아래 7가지 경우의 합을 계산하면 됩니다. \( dp_{N-1, a, b, c-1} \) \( dp_{N-1, a, b-1, c} \) \( dp_{N-1, a, b-1, c-1} \) \( dp_{N-1, a-1, b, c} \) \( dp_{N-1, a-1, b, c-1} \) \( dp_{N-1,..

난이도: Gold I 태그 더보기 Dynamic Programming Line Intersection 풀이 0. 풀이를 읽기 전: 정의 더보기 \( P_{i} \)는 \( i \)번째 점의 위치를 의미합니다. 시작점은 \( P_{0} \), 즉 \( 0 \)번째 점으로 표현합니다. \( L_{i} \)는 \( i \)번째 울타리의 위치 (선분)을 나타냅니다. \( H_{i} \)는 \( i \)번째 울타리의 높이를 나타냅니다. 1. \( P_{i} \)에서 \( P_{j} \)로 성공적으로 이동할 수 있는 확률은? 더보기 어떤 울타리 \( L_{k} \)와 \( \overline{P_{i} P_{j}} \)가 교차한다면, 이 울타리를 뛰어넘을 확률은 \( \frac{1}{H_{k}} \)가 됩니다. 그러..

난이도: 538 태그 더보기 Counting Brute Force 풀이 1. 순서쌍에 대해 생각해보기. 더보기 \( r, g \)가 고정되었다고 해봅시다. 이 때, 가능한 \( b \)의 개수는 얼마나 될까요? \( rR + gG + bB = N \)을 만족시켜야 하는데, \( b \)를 제외하고는 모두 고정된 값이니 가능한 값은 1가지이거나 0가지가 됩니다. 즉, \( r, g \)에 대해서만 브루트포스를 하면서 \( b \)의 가능성 여부를 따지면 되겠죠. 2. \( r, g \)가 고정될 때, 가능한 \( b \)가 존재하는 경우는? 더보기 \( rR + gG + bB = N \)라는 식을 약간 변형해서, \( b \)만 우변에 남겨봅시다. \( b = \frac{N - rR - gG}{B} \) ..

난이도: Gold IV 태그 더보기 Precomputation Primality Test 풀이 1. \( K \)의 범위가 많이 작은데... 더보기 가능한 모든 소수 \( p \)에 대해 \( 2^p - 1 \)의 소인수분해 결과를 미리 저장해둡시다. 이는 제출 코드가 아닌 다른 코드를 사용해서 전처리를 해주는 방식으로 처리할 수 있습니다. 2. 주의사항 더보기 \( 2^{61} - 1 \)은 소수입니다. 만약 \( O(\sqrt{N}) \) 시간의 소수 판정/소인수분해를 하고 있다면, \( K = 61 \)에서 continue를 하는 걸 추천합니다. 사실 \( K = 61 \)만 제외하면 그냥 제출 코드에서 돌려도 될 정도로 빠르게 돌아갑니다. 3. 코드(로 추정) 더보기 1 2 3 4 5 6 7 8 ..

난이도: 2100 태그 더보기 Greedy Graph Theory Connected Component Disjoint Set Union Priority Queue 풀이 1. 다른 Region에 있는 도시는 몇 번 연결해야 하는가? 더보기 다른 Region에 있는 도시를 하나 연결할 때마다 연결 요소의 개수가 1씩 줄어들게 됩니다. 그러므로, 입력된 그래프의 연결 요소를 \( c \)라고 할 때, \( q-c \)번 연결해야겠죠. 2. 답이 No인 경우는? 더보기 [1]에 따르면, 연결 횟수인 \( p \)는 \( 0 \le p \le q-c \)여야 합니다. 이를 만족하지 못한다면, 답은 No가 되겠죠. No가 나오는 케이스가 하나 더 있는데, \( m = 0, p \neq 0, q = n \)입니다. ..

난이도: Silver IV 태그 더보기 Implementation (그러니까... 뭐 넣어야 할 지 모르겠어요) 풀이 1. 일단 기록해보자. 더보기 지문에 나온 7마리의 소에 대해, 짜낸 우유의 값을 0으로 설정해둡니다. 그 뒤로는, 소 이름과 짜낸 양에 맞춰서 milk[cow] += amount; 해주면 되겠죠. 2. 가장 적게 우유를 짜낸 소는? 더보기 사실 누가 가장 적게 짜냈는지는 중요하지 않습니다. 그냥 가장 적게 나온 우유의 양만 알면 됩니다. 그러니, 그냥 우유의 양의 최솟값을 찾으면 됩니다. 3. 그 소보다 더 많이 짜낸 소들 중, 우유를 가장 적게 짜낸 소는? 더보기 평소에 최솟값 찾는 방식이랑 비슷하게 하면 됩니다. 달라지는 점은, 우유의 양이 최솟값과 동일하면 확인하지 않고 패스한다는..

난이도: Silver IV 태그 더보기 Euclidean Algorithm → Greatest Common Divisor 풀이 1. 풀이 더보기 하나의 \( i, j \) 쌍에 대해, \( \text{GCD}(A_{i}, A_{j}) \)는 log 시간에 알아낼 수 있습니다. 이러한 쌍이 \( O(N^2) \)개 있으니, 이를 다 돌려주면 됩니다. 2. 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int gcd(int a, int b){ return b==0 ? a : gcd(b, a%b); } int arr[120]; void Main(){ int t; cin >> t; while (t--){ int n; cin >> n; for (int i = 1; i > arr[i]..