hibye1217 hibye1217

난이도: 178 번역 더보기 Holidog는 굉장히 똑똑한 개입니다. 얼마나 똑똑하냐면, 덧셈과 소수 판별을 할 수 있습니다! Holidog에게 어떠한 양의 정수를 주고 이 수가 소수인지 묻는다면, 소수라면 WANWAN이라고 짖고, 아니라면 BOWWOW라고 짖습니다. 당신은, 이 Holidog에게 \( 1 + 2 + 3 + \ldots + N \)이 소수인지 묻기로 했습니다. 이 때 Holidog가 어떻게 짖을 지 출력하세요. 소수란, \( 2 \) 이상의 양의 정수 중 \( 1 \)과 자기 자신을 제외한 다른 양의 정수로 나누어지지 않는 수를 의미합니다. 예로, \( 2 \), \( 3 \), \( 17 \)은 소수이지만, \( 1 \), \( 10 \)은 소수입니다. 태그 더보기 Mathematics..

난이도: 1393 태그 더보기 Recursion Divide and Conquer 풀이 1. 어떤 수 \( N \)에 있는 1의 개수를 세보자. 더보기 \( N \)에 있는 1의 개수는, \( N \)을 계속 10으로 나누면서 1의 자리가 1인지 계속 봐주면 됩니다. 2. [1]을 조금 다르게 생각해보자. 더보기 [1]에서 구하는 과정을 잘 생각해보면, (10 이상의 자리에 있는 1의 개수) + (1의 자리에 있는 1의 개수)로 표현할 수 있습니다. 3a. \( 0 \) 이상 \( N \) 이하의 모든 정수에 있는 1의 개수를 세는 방법 더보기 \( f(n) \)를 \( 0 \) 이상 \( n \) 이하의 모든 정수에 있는 1의 개수라고 정의하고 \( g(n) \)을 \( n \)에 있는 1의 개수라고 ..

난이도: 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} \) = 상태 ..

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

난이도: 1739 태그 더보기 Double Counting Combinatorics Prefix/Suffix Query 풀이 1. '?'를 제외하고 생각해보자. 더보기 문자열에 '?'가 없다고 가정해봅시다. 그럼, 문제의 답은 그냥 만들 수 있는 "ABC"의 개수가 됩니다. 이 개수는 어떻게 찾을까요? 중심에 있는 'B'를 하나로 고정해봅시다. 그럼, 그 문자를 사용해서 만들 수 있는 "ABC"의 개수는 왼쪽에 있는 'A'의 개수 × 오른쪽에 있는 'C'의 개수가 됩니다. 문제의 답은 이를 모든 'B'에 대해 고려해주면 됩니다. // 중심에 있는 'B'가 다르기 때문에, 한 문자열을 두번 셀 걱정은 하지 않아도 됩니다. 2. 어떤 문자 'B'를 고정시킬 때, '?'를 포함해서 계산하는 방법은? 더보기 이..

난이도: 2125 태그 더보기 Combinatorics Addition Rule Probability Theory Dynamic Programming using Probability Modular Multiplicative Inverse 풀이 1. 앞에 있는 \( N \)개만 두고 볼 때, \( K \)번 추첨해서 \( M \)개를 뽑을 확률은? 더보기 \( dp_{n, m, k} \) = 앞에 있는 \( n \)개만 두고 볼 때, \( k \)번 추첨해서 \( m \)개를 뽑을 확률로 정의해봅시다. 그리고, 이에 맞게 초항부터 설정해봅시다. \( n k \)인 경우: 추첨 횟수보다 더 많이 뽑았다는데, 불가능..

난이도: 1824 // Experimental 번역 더보기 C. 1억 번이 넘는 계산 Takahashi는 \( N^2 \)회의 많은 계산이라는 방식으로 본인의 계산 능력을 늘리려 합니다. \( N^2 \)회의 많은 계산은 아래와 같이 진행됩니다. 우선, \( N \times N \) 크기의 행렬을 준비합니다. 그리고, 행렬의 맨 왼쪽 줄의 왼쪽에는 \( A_{i} \)를 차례로 적고, 맨 윗줄의 위에는 \( B_{j} \)를 차례대로 적습니다. 이제, \( (i, j) \)의 위치에 있는 칸에는 \( A_{i} \times B_{j} \)를 적습니다. Takahashi는 이를 너무 간단하게 끝냈기 때문에, 이렇게 적은 \( N^2 \)개의 수를 정렬해보기로 했습니다. 이 때, 정렬 후 앞에서부터 \( K..