본문 바로가기

전체 글

 (117)
백준 8506번: Leonardo's Numbers https://www.acmicpc.net/problem/8506 8506번: Leonardo's Numbers The famous Fibonacci numbers are not the only discovery of Leonardo of Pisa, also known as Fibonacci. Let us denote L0 = L1 = 1 and Li+1 = Li + Li-1 + 1 for i ≥ 1. The sequence (Li) is also called Leonardo's numbers. Today, 800 years after Leonardo Fib www.acmicpc.net 이 문제를 풀 때 크게 두 가지 방향으로 접근할 텐데, Berlekamp - Massey 같은 방법론으로 점화식을 얻어..
백준 28294번: 프랙탈 https://www.acmicpc.net/problem/28294 28294번: 프랙탈 첫째 줄에 정수 $N$, $a$가 공백으로 구분되어 주어진다. $(3 \le N \le 10^9; 1 \le a \le 10^9)$ www.acmicpc.net 단계별로 도형의 둘레를 구해보며 접근하면 규칙이 바로 나오는 문제입니다. 아무 과정도 거치지 않은 상태의 둘레의 길이는 $N \times N^{a}$ 입니다. 그 다음, 한 변이 $N^{a-1}$인 도형을 그리면, 증가하는 둘레의 길이는 $N \times (N-2)N^{a-1}$ 입니다. 3단계에서 증가하는 둘레의 길이는 $N \times (N-1) \times (N-2)N^{a-2}$ 입니다. 4단계에서 증가하는 둘레의 길이는 $N \times (N-1)^..
백준 6673번: Firepersons https://www.acmicpc.net/problem/6673 6673번: Firepersons The input consists of several instances. Each instance is described on a single line containing the following integers separated by a single space: k, a0, , ak-1, b1, , bk, i. Here 1
백준 27875번: 파이파이 https://www.acmicpc.net/problem/27875 27875번: 파이파이 첫째 줄에 $n$이 주어진다. $(1\le n \le 314\,159)$ www.acmicpc.net 인터넷 검색으로 어떻게든 레퍼런스를 찾기만 하면 매우 쉬워지는 문제였습니다. 일반적으로 어떤 실수 $x$의 소수점 아래 $N$번째 수를 구하기 위해서는 $10^{N} \times x$을 관찰합니다. 이 문제에서 $\pi ^{2}$의 소수점 아래 $N$번째 수는, 16진법이므로, $16^{N} \times \pi ^{2}$를 얻어야 할 것입니다. 여기서 $\pi ^{2}$의 16진법 표현을 얻는 방법이 문제의 핵심이었습니다. $\pi$의 16진법 표현을 안다면 어쩌면 가능할 수도 있습니다만 소스 코드 길이 제한에 걸..
백준 27318번: 세상에서 가장 달달한 디저트 만들기 (integer) https://www.acmicpc.net/problem/27318 27318번: 세상에서 가장 달달한 디저트 만들기 한별이는 튀르키예와 그리스의 전통 젤리인 로쿰을 만들고 있다. 로쿰은 녹말, 물, 설탕, 레몬즙 등을 냄비에 넣고 끓여서 걸쭉해질 때까지 저어준 다음, 겉에 슈가파우더를 뿌려서 굳히는 디저 www.acmicpc.net 행렬 거듭제곱이 더 떠올리기 쉬운 풀이같긴 한데, 일반항을 구해서 풀 수 있는 문제이므로 일반항을 구하는 방법도 소개합니다. 이 글에서 $$V(N,M) = (12N-16)^{M}$$ 이고 $$S(N,M) = (4N-4) \times S(N,M-1) + (24N-48) \times V(N,M-1)$$ 이라는 걸 이미 설명했으니, 해당 지점부터 이어가겠습니다. 덧붙여, $$V(..
백준 27318번: 세상에서 가장 달달한 디저트 만들기 (matrix) https://www.acmicpc.net/problem/27318 27318번: 세상에서 가장 달달한 디저트 만들기 한별이는 튀르키예와 그리스의 전통 젤리인 로쿰을 만들고 있다. 로쿰은 녹말, 물, 설탕, 레몬즙 등을 냄비에 넣고 끓여서 걸쭉해질 때까지 저어준 다음, 겉에 슈가파우더를 뿌려서 굳히는 디저 www.acmicpc.net 문제에서는 $N$과 $M$이 달라질 때마다 완전히 꽉 차있는 $\left ( N^{M} \right )^{3}$짜리 정육면체로부터 시작하지만, 어차피 최종 결과물은 $N,M$값에 상관없이 부피 1짜리 정육면체들로 이루어져있습니다. 즉, $N$을 고정시킨 뒤, $M$을 하나씩 늘리며 이전 단계의 로쿰이 몇 번 나타나는지 확인하는 게 떠올리기 쉬운 풀이 같습니다. 그림으로 주어..
백준 25028번: Fully Generate https://www.acmicpc.net/problem/25028 25028번: Fully Generate 양의 정수 만으로 이루어진 단조 증가 수열 $G$가 있다. 이 수열에서 $G_i$는 $i$가 $1$ 이상의 정수일 때 정의되며, $G$에서 $i$가 등장하는 횟수를 나타낸다. 정확히 말하면, $G$는 $i$가 $G_i$번 나타나 www.acmicpc.net 풀이를 설명하기가 상당히 난해한 문제라고 생각합니다. 우선, 글에 나오는 수열은 Golomb Sequence 등으로 불리며 Wikipedia, OEIS에 문서가 있습니다. 가장 단순한 풀이는 물론 $G_{i}$를 모두 구하는 것입니다. 이는 append같은 메서드를 지원하는 컨테이너를 써서 쉽게 구현할 수 있는데, space complexity..
백준 9819번: Color Change of Go Game Pieces https://www.acmicpc.net/problem/9819 9819번: Color Change of Go Game Pieces Assume that there are lots of two colors of black and white Go Game Pieces in a box, we take out n Go Game Pieces (0 < n < 129, n is a natural number) each time from the box, among which all the m pieces taken out earlier are white and the latter pieces ar www.acmicpc.net 단순히 문제를 그대로 시뮬레이션 하는 것으로 풀리는 문제이지만, $k$가 충분히 클 때 복..

티스토리툴바