waystring 님의 블로그

https://www.acmicpc.net/problem/2622 이 문제를 $\mathcal{O} (1)$과 $\mathcal{O} (n)$의 시간으로 해결하겠다.$\mathcal{O} (1)$ 알고리즘https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=b9b5d4997aad1fef74e084e708cc8d49d7466b70 증명은 위의 논문 내용을 바탕으로 한다. 둘레가 $n$이고 세 변이 자연수인 삼각형의 수를 $T_{n}$이라고 하자. 그러면 $$T_n = \begin{cases} \text{round}\left(\displaystyle \frac{(n + 3)^2}{48}\right) & \text{if} \; n \; \text{is..

학교 선생님이 가끔 하던 특이한 방식의 가위바위보 게임의 확률을 계산해 보겠다. 방식은 다음과 같다.1. $P$와 $Q$는 일어서서 서로의 등을 맞대며 손을 들고 서 있다.2. 둘은 비기지 않고 승패의 결과가 나올 때까지 가위바위보를 계속한다(둘은 상대가 무엇을 냈는지 모르며, $J$가 승패의 결과가 나오면 그만하라고 하고, 비기면 다시 하라고 한다. 무한 번 비기지는 않는다)3. $J$가 $P$한테 물어본다. “지금 가위바위보 낸 거 바꾸고 싶으면 바꾸고, 안 바꾸고 싶으면 바꾸지 마”. 이 만약 바꾸지 않는다면, $J$가 결과를 알려준다. 만약 바꾼다면 $J$는 $Q$한테 물어본다. “지금 가위바위보 낸 거 바꾸고 싶으면 바꾸고, 안 바꾸고 싶으면 바꾸지 마”. $Q$가 만약 바꾸지 않는다면, $J..

궁극적으로 아래 문제를 해결해 보겠다.임의의 자연수 $n, m$에 대해 $$\sum_{x=1}^{n}\prod_{y=0}^{m}(x+y)=\frac{1}{m+2}\prod_{x=0}^{m+1}(x+n)$$가 항상 성립함을 증명하여라.두 가지 방법으로 증명해 보겠다.수학적 귀납법별로 좋아하는 방법은 아니지만 현실적으로 시험이나 타임어택이라면 가장 성공률이 높은 방법이다. 먼저 $n=1$인 경우 좌변은 $(m+1)!$이고, 우변이 $\displaystyle \frac{1}{m+2} \times (m+2)!=(m+1)!$여서 성립한다. $n=k$일때 성립한다 가정하고 $n=k+1$일 때 성립함을 증명하면 된다. $$\sum_{x=1}^{k+1}\prod_{y=0}^{m}(x+y)=\sum_{x=1}^{k}\p..

궁극적으로 다음 문제를 해결해 보겠다(내가 만듦).임의 자연수 $n$에 대해 $$\sum_{i_{1}=1}^{n} \sum_{i_{2}=1}^{i_{1}} \sum_{i_{3}=1}^{i_{2}} \cdots \sum_{i_{100}=1}^{i_{99}} a_{i_{100}} = 1$$를 항상 만족시키는 수열 $a_{i}$가 있다. $a_{98}$을 구하여라.보통 시그마가 100개 중첩된 것은 처음 보는 형식이라서 감도 안 온다. 사실 이전 글에서 설명한 시그마 역연산을 이용해 시그마 100개를 하나씩 하나씩 제거하면 된다(물론 규칙이 나온다). 먼저 다음과 같은 수열을 정의하자. $$\sum_{i_{1}=1}^{n} \sum_{i_{2}=1}^{i_{1}} \sum_{i_{3}=1}^{i_{2}} \c..