본문 바로가기

분류 전체보기

 (116)
백준 26309번: Etched Emerald Orbs https://www.acmicpc.net/problem/26309 26309번: Etched Emerald Orbs If there is no solution, output $-1$. Otherwise, output two distinct integers $x$ and $y$ separated by a blank where $\frac{2}{k} = \frac{1}{x} + \frac{1}{y}$ and $1 ≤ x < y ≤ 2^{125}$. If there are multiple solutions, output the solution minimizing $x www.acmicpc.net 문제의 상황은 주어지는 자연수 $k$ 에 대해 다음 조건을 만족하는 서로 다른 자연수 $x$, $y$ 를 찾으라는..
백준 30521번: Mike Sees The Storm (Large) https://www.acmicpc.net/problem/30521 30521번: Mike Sees The Storm (Large) $N=2$, $K=2$일 때 Mike가 얻을 수 있는 수열의 목록은 [$-1, -2, -1, 0$], [$-1, 0, -1, 0$], [$-1, 0, 1, 0$], [$1, 2, 1, 0$], [$1, 0, 1, 0$], [$1, 0, -1, 0$] 총 $6$가지로, 최댓값의 $K$제곱을 합하면 $7$이다. www.acmicpc.net 카탈란 수의 응용입니다. 먼저 주어진 문제를 격자 속의 최단 경로 문제로 환원합니다. 칠판에 적힌 숫자를 $a$에서 $a-1$ 로 바꾸는 연산을 오른쪽으로 한 칸 이동하는 것으로, $a$에서 $a+1$로 바꾸는 연산을 위로 한 칸 이동하는 것..
백준 30354번: Sum of Product of Binomial Coefficients https://www.acmicpc.net/problem/30354 30354번: Sum of Product of Binomial Coefficients You are given integers $N$ and $K$. For a positive integer $k$, $f(k)$ is defined as follows. The Sum of $\binom{N}{a_1} \times \binom{a_1}{a_2} \times \cdots \times \binom{a_{k-1}}{a_k}$ for all integer sequences $(a_1, a_2, \dots, a_k)$ that satisfy the www.acmicpc.net 문제의 설명을 읽어봤을 때, 진짜 모든 $a_{1}$ 부터 $a_{k}$..
백준 5647번 : 연속 합 https://www.acmicpc.net/problem/5647 5647번: 연속 합 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, q값이 주어진다. q는 1014보다 작은 양의 정수이다. 입력의 마지막 줄에는 0이 하나 주어지고, 입력 www.acmicpc.net 간단한 모델링을 해보면, 정수 $x$부터 $p$개 정수의 합은 다음과 같습니다. $$ x + (x+1) + \cdots + (x+p-1) = \frac{p(2x+p-1)}{2} $$ 문제의 서술을 그대로 따라가면, 이는 $x+p$부터 $q$개 정수의 합과 같아야 하며 다음 식으로 이어집니다. $$ \frac{p(2x+p-1)}{2} = \frac{q(2x+2p+q-1)}{2} $$ 아무 고민도..
백준 7501번: Key https://www.acmicpc.net/problem/7501 7501번: Key Hackers often have to crack passwords for different data encryption systems. A novice hacker Bill faced such a problem one day. After performing several experiments he noticed regularity in the formation of an encryption key. He knew that a key is an odd i www.acmicpc.net 케이스 분류를 차근차근 해보면 쉽게 접근할 수 있는 문제입니다. Case 1 : K가 소수일 때 Wilson's Theorem에 따르면, ..
백준 30169번: Primes and Multiplication https://www.acmicpc.net/problem/30169 30169번: Primes and Multiplication In the first example, $f(10, 1) = g(1, 2) \cdot g(1, 5) = 1$, $f(10, 2) = g(2, 2) \cdot g(2, 5) = 2$. In the second example, actual value of formula is approximately $1.597 \cdot 10^{171}$. Make sure you print the answer modulo $(10^{9} + 7)$. In the third www.acmicpc.net 문제에서 나오는 $f(x,y)$와 $g(y,p)$의 정의를 잘 관찰해보면, $$ \prod_{i..
백준 27743번: 어려운 하노이 탑 https://www.acmicpc.net/problem/27743 27743번: 어려운 하노이 탑 하노이 탑은 다음 규칙을 지키면서, 첫 번째 막대기에 꽂힌 원판들을 그 순서 그대로 세 번째 막대기로 옮기는 놀이다. 한 번에 $1$개의 원판만 옮길 수 있다. 가장 위에 있는 원판만 이동할 수 있 www.acmicpc.net $N=4$, $M=3$ 정도인 상황을 시뮬레이션 돌려보면 감을 잡을 수 있습니다. 우선, 각 기둥을 왼쪽에서부터 peg 1, 2, 3 이라고 하겠습니다. 그리고 크기 $N$의 원판이 번호 $1$부터 $M$에 대해 내림차순으로 쌓인 상황을 $N \downarrow$로 표현하겠습니다. 다시 말해 문제에서 주어진 초기 상황이 다음과 같이 표현된다는 뜻입니다. $$ \begin{matrix..
백준 24415번: 편지 https://www.acmicpc.net/problem/24415 24415번: 편지 첫번째 줄에는 공백을 사이에 두고 현수가 작성한 편지의 길이 $N$, 규칙 목록의 길이 $C$, 데미지를 입은 횟수 $K$ 가 정수로 주어진다. $(1 \le N \le 100, 1 \le C \le 10^5, 1 \le K \le 10^{12})$ 두번째 줄에 www.acmicpc.net 이 문제가 생각나기도 합니다. 기본적인 아이디어는 $C$개의 규칙을 모두 합친 것을 $\lfloor \frac{K}{C} \rfloor$ 번 반복하고, $1$번째 규칙부터 $K \;\; \% \;\; C$ 번째 규칙까지 마저 진행한다는 것입니다. 각각의 규칙을 행렬로 나타내는 아이디어는 기본적으로 identity matrix에서 특..

티스토리툴바