hibye1217 hibye1217

난이도: Bronze III 태그 더보기 Case Work Leap Year Detection 풀이 1. m월 m일의 m일 전은? 더보기 간단히 생각해보면, m월 m일에서 m을 뺀 값인 m월 0일이 됩니다. 하지만 0일이라는 건 없으니, m-1월의 말일로 넘어가게 되겠죠. 즉, m월 m일의 m일 전은 m-1월 말일이라는 것을 의미합니다. 2. 구현 방식 더보기 아래는 구현을 편하게 해줄 몇몇가지 추천입니다. month[m]: m월에는 몇 일까지 있는지 저장해두는 배열입니다. // 특히 이 문제에서는 month[0] = month[12]로 하는 걸 추천합니다. leap(y): y년이 윤년인지 판별하는 함수입니다. 3. 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 int day[15] ..

난이도: Silver V 태그 더보기 Sort 풀이 0. 시작하기 전: 간단한 정의 더보기 \( A_{i, x} \)은 \( i \)번째 참가자가 \( x \)점을 준 참가자의 번호를 의미합니다. 이 값은 \( i \)번째 참가자가 \( N-x \)위를 준 참가자의 번호와 일치합니다. 1. 각 참가자의 점수는 어떻게 정할까? 더보기 \( i \)번 참가자의 점수를 계산해봅시다. 이는, \( A_{j, x} = i \)를 만족하는 모든 \( (j, x) \) 순서쌍에 대해, \( x \)점씩 추가로 더해주면 됩니다. 참가자의 점수를 1명씩 계산해야 할 필요는 없으니, \( A_{i, x} \)를 돌아보면서 \( A_{i, x} \)번 참가자에 \( x \)점을 더해주면 됩니다. 이 뒤로 남은 건 점수 순 ..

난이도: Platinum III 태그 더보기 Convex Hull 풀이 1. 가장 먼 두 점의 후보가 될 수 있는 점은? 더보기 우선,입력받은 점들을 토대로 볼록 껍질을 만들어 봅시다. 볼록 껍질을 만드는 이유는, 볼록 다각형에서 가장 먼 두 점은 경계에 있는 두 점이기 때문입니다. // 그렇지 않다면, 경계를 만날 때까지 더 늘릴 수 있겠죠. 다만 이게 가장 먼 두 점이 볼록 껍질에 포함된 점뿐임을 의미하진 않을수도 있습니다. // 가장 먼 두 점이 꼭짓점이 아니라 변에 위치한 점이었다면? 그 점을 실제로는 다시 만들어낼 수 없으니 잘 생각해봐야겠죠. 즉, 이 부분에 대해서는 추가적으로 생각을 해봐야겠죠. 다행히도, 볼록 다각형에서 가장 먼 두 점은 항상 두 꼭짓점이 됩니다. // 두 점을 잡아보고, ..

난이도: Bronze I 태그 더보기 Geometry 풀이 1. 점이 직사각형 안에 있는지 확인하는 방법은? 더보기 직사각형의 좌측 하단 점을 \( (x_1, y_1) \), 우측 상단 점을 \( (x_2, y_2) \)라고 합시다. 우리가 입력받은 점이 \( (x, y) \)라면, 점이 직사각형 안에 있기 위해서는 \( x \)좌표는 \( x_1 \) 이상 \( x_2 \) 이하여야 하고, \( y \)좌표는 \( y_1 \) 이상 \( y_2 \) 이하여야 합니다. 식으로 쓰자면, \( x_1 \le x \le x_2 \), \( y_1 \le y \le y_2 \)가 됩니다. 2. 점이 원 안에 있는지 확인하는 방법은? 더보기 원의 중심을 \( (x_1, y_1) \), 반지름을 \( r \)이라고..

난이도: 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}} \)가 됩니다. 그러..

난이도: 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 ..