본문 바로가기

전체 글

 (117)
백준 26035번: $0101$ https://www.acmicpc.net/problem/26035 26035번: $0101$ $N\times M$ 크기의 배열의 각 칸에 $0$과 $1$중 하나를 적는다. 이때, 모든 $2\times 2$ 크기의 부분 배열 안에 적힌 수의 합이 $2$로 같아지도록 배열을 채우는 방법의 수를 구하여라. www.acmicpc.net $N$을 편하게 2로 고정해놓고 $M$을 늘리면서 관찰하면 쉬운 문제입니다. 또한, 관찰할 때 저의 경우 위에서부터 1행을 채우고 그 아래 행을 채운다는 느낌으로 접근했습니다. 예제에 나온 $M=4$, $N=2$의 경우를 한 번 보게 되면 1행이 $0101$, $1010$일 경우를 제외하고 모두 1행이 정해지면 2행도 단 하나로 결정됐습니다. $M=3$인 경우 $101$, $0..
백준 25569번: My뷰 꾸미기 https://www.acmicpc.net/problem/25569 25569번: My뷰 꾸미기 카카오 뷰는 사용자가 관심을 가질 만한 주제를 분석하고, 이를 바탕으로 큐레이팅을 진행하는 카카오톡의 서비스이다. '발견'을 통해 흥미로운 주제의 콘텐츠를 탐색하고, 마음에 드는 콘텐츠 www.acmicpc.net 주어진 예제의 답이 왜 54인지 생각해보면 다음을 알 수 있습니다. $$ 54 = \binom{1}{1}\binom{2}{1} \times \left ( \binom{3}{1}\binom{2}{1} + \binom{3}{2}\binom{2}{2} \right ) \times \binom{1}{1}\binom{3}{1} $$ 이를 이해했다면 문제의 답을 $N$, $A_{i}$, $B_{i}$에 대해 ..
백준 24930번: Ordinary Ordinals https://www.acmicpc.net/problem/24930 24930번: Ordinary Ordinals Sets, sets, sets. Everything in math is just a set. Even the natural numbers can be represented as sets. For example, we can represent the the number $0$ as the empty set $\{\}$. The number $1$ can be represented as $\{\{\}\}$. But what about $2$? Conside www.acmicpc.net 폰 노이만이 자연수를 정의한 것을 차용한 문제입니다. $N$에 대응되는 괄호 문자열의 길이를 $a_{N}$라고 ..
백준 13630번: Buses https://www.acmicpc.net/problem/13630 13630번: Buses The input contains a single line, containing three integers N, K and L, representing respectively the total length, in meters, of the line Ricky is considering, K indicates the number of different colors for micro-buses, and L represents the number of diff www.acmicpc.net 문제를 잘 읽으면 결국 $1 \times N$ 직사각형을 $1 \times 5$, $1 \times 10$ 블록으로 타일링하는 방법..
백준 25962번: 선우의 셋리스트 https://www.acmicpc.net/problem/25962 25962번: 선우의 셋리스트 첫 번째 줄에 선우가 공연을 위해 준비해야 하는 가능한 셋리스트의 경우의 수를 $1\,000\,000\,007$($=10^{9}+7$)로 나눈 나머지를 출력하시오. 셋리스트를 구성할 수 없다면 정답은 $0$이다. www.acmicpc.net 잘 관찰하면 이 문제는 $1 \times N$ 크기의 직사각형을 $1 \times 1$부터 $1 \times 5$ 크기의 블록으로 타일링하는 경우의 수를 구하는 문제와 같다고 할 수 있습니다. 몇 가지 정의하겠습니다. 1분짜리, 2분짜리, 3분짜리, 4분짜리, 5분짜리 노래의 개수를 각각 $M_{1}$, $M_{2}$, $M_{3}$, $M_{4}$, $M_{5}$ 라고..
백준 25974: 거듭제곱의 합 1 https://www.acmicpc.net/problem/25974 25974번: 거듭제곱의 합 1 $1$부터 $n$까지 모든 자연수의 $p$ 거듭제곱의 합을 $10^9+7$로 나눈 나머지를 구하시오. 다시 말해, $$\left(\sum_{k=1}^{n}k^p\right)\mod\left(10^9+7\right)$$ 을 구하시오. www.acmicpc.net [BOJ1492]에서 지수 크기의 상한을 1000으로 높인 버전입니다. 따라서 풀이는 백준 1492번: 합 과 같습니다. 다음은 제 코드입니다. #include #define mod 1000000007 long long array_nCk_modulo[1002][1002]; // array of (nCk) mod (10^9 + 7), 0
백준 1908번: 곱셈 전개식 https://www.acmicpc.net/problem/1908 1908번: 곱셈 전개식 첫째 줄에 식을 전개하였을 때의 길이를 출력한다. 단, 길이가 매우 길어질 수 있으므로 이를 10,000으로 나눈 나머지만을 출력한다. www.acmicpc.net 본문에서 나온 그대로 $N$ 차식의 길이를 구하는 문제인데, 첫 발상과 case work에서 까다로움을 느낄 수 있는 문제입니다. 우선 $N$ 차식의 형태를 간략하게 몇 개 항만 써보겠습니다. $$ x^{N} + \left ( a_{1} + a_{2} + \cdots + a_{N} \right ) x^{N-1} + \left ( a_{1}a_{2} + a_{1}a_{3} + \cdots + a_{2}a_{3} + \cdots + a_{N-1}a_{N} ..
백준 11333번: 4×n 타일링 https://www.acmicpc.net/problem/11333 11333번: 4×n 타일링 각 테스트 케이스마다 문제의 정답을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 원래는 정석적인 도미노 타일링 문제가 아니어서 손을 안 대려 했습니다. 그런데 호기심에 다른 블로그 풀이들을 서치해보니까 profiling을 이용해서 딱히 선형점화식 없이 풀더라고요. 물론 그것들도 좋은 풀이인데 저는 선형점화식을 찾아보고 싶었습니다. (참고로, 이 문제가 딱히 [BOJ11726] 2xn타일링에서 유래했다고 보긴 어려울 것 같습니다. 물론 문제 상황은 비슷하지만, 점화식의 형태나 유도과정이 다소 다르다고 생각합니다. 개인적으로 그보다는, [BOJ13976] 타일 채우기..

티스토리툴바