본문 바로가기

전체 글

 (116)
백준 21854번: Monsters https://www.acmicpc.net/problem/21854 21854번: Monsters The 2017 International Congress of Monsters gathers n monsters coming from all over the world. Their chairman has to solve the following problem: if the ith monster (1 ≤ i ≤ n) has ki fingers, indexed from 0 to ki - 1, so he can lift j of those fingers www.acmicpc.net 오랜만에 보는 쉬운 문제입니다. 예제에서 다음 세 가지 특징을 알 수 있습니다. $\left ( 1 \right )$ 아무것도 안 쓰..
백준 1529번: 동민 수열 https://www.acmicpc.net/problem/1529 1529번: 동민 수열 첫째 줄에 Numbers 배열의 크기 N과 L이 주어진다. N은 50보다 작거나 같은 자연수이고, L은 1,000,000,000보다 작거나 같은 자연수이다. 둘째 줄에 Numbers배열에 들어있는 수가 주어진다. 각각의 수는 1,00 www.acmicpc.net 이 문제는 이전 두 포스팅과 아주 유사한 문제입니다. ( 12878번: Blocks ) ( 19587번: 객실 배치 ) 우선, 다음 성질에 따라 4와 7로만 이루어진 수를 찾습니다. 금민수는 4와 7로만 이루어진 수이다. $A\left [ i \right ]$ 는 금민수이다. $\left ( 0\leq i < L \right )$ 주어진 숫자 $N$ 개에서 ..
백준 19587번: 객실 배치 https://www.acmicpc.net/problem/19587 19587번: 객실 배치 1층 호텔이면 101호에 배치한 경우, 102호에 배치한 경우, 아무 호실에도 배치하지 않는 경우, 총 3가지 경우를 생각할 수 있다. www.acmicpc.net 이전 포스팅과( 12878번: Blocks ) 방법론이 비슷한 문제입니다. 다만, 이전 포스팅에서는 모든 state의 경우의 수를 문제에서 답으로써 요구하지는 않았습니다. 그 점에서, 이번 문제는 정답에 해당하는 경우를 여러 state로 나눠 본다는 차이가 있습니다. $N=1$ 일 때의 예제 해설에 따라서, $N$ 층까지 사람을 조건에 맞게 배치한 경우를 생각해 봅시다. 이때, $N$ 층에 대하여 다음과 같은 state 들이 존재한다고 할 수 있습니다..
백준 12878번: Blocks https://www.acmicpc.net/problem/12878 12878번: Blocks N개의 블록이 일렬로 놓여져 있습니다. 민호는 각각의 블록들을 빨, 주, 노, 초 네가지 색중 한가지 색으로 칠하려 합니다. 민호는 문득 빨간색으로 칠해진 블록의 개수와 노란색으로 칠해진 블 www.acmicpc.net 우선 이 문제에서 구하고자 하는 경우의 수를 관찰하고자 합니다. 편의상 이하에서 짝수라는 표현을 0을 포함하는 2로 나눠떨어지는 정수들의 집합으로 정의하겠습니다. N개의 블록들을 모두 칠했을 때 빨간색과 노란색으로 칠해진 블록의 개수가 2로 나누어 떨어지게 칠하는 경우의 수 예제를 보면, $N=1$ 일 때 답은 2입니다. 전체 블록이 1개이므로 조건을 만족하기 위해 빨간색 또는 노란색으로 칠해진..
백준 2709번: 가장 작은 K www.acmicpc.net/problem/2709 2709번: 가장 작은 K 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 50)가 주어진다. 각 테스트 케이스는 정수 1개로 이루어져 있고, 이 수는 R(1 ≤ R ≤ 20)이다. www.acmicpc.net 이 문제에서 $R\leq 19$인 경우까지는 단순하게 구할 수 있습니다. $R=20$의 경우는 C에서는 스트링으로 처리해야하는데, 이 부분이 귀찮았던 저는 구글링으로 해결했습니다.(acmgnyr.org/year2008/h.out) 위 링크를 통해 물론 모든 $R$에 대한 정답을 알고 쉽게 정답 코드를 작성할 수도 있습니다. 또는 아래 설명할 원리를 통해 미리 각 $R$ 값에 대한 정답을 구한 뒤, 이를 배열에 집어넣는 방식으로 구현해도 됩니다...
백준 12728번: n제곱 계산 www.acmicpc.net/problem/12728 12728번: n제곱 계산 이 문제에서 숫자 (3 + √5)n 에 대한 소수점 앞에 마지막 세 자리를 찾아야합니다. 예를 들어, n = 5 일 때 (3 + √5)5 = 3935.73982 ... 이므로 답은 935입니다. n = 2 인 경우 (3 + √5)2 = 27.4164079 … 이므로, www.acmicpc.net 이전에 올렸던 글과 비교했을 때 $n$ 의 범위가 조금 더 커졌습니다. (백준 12925번: Numbers) 그 외의 차이가 없습니다. 코드는 다음과 같습니다. #include typedef struct { int array[2][2]; } Matrix; Matrix matrix_multiply_modular (Matrix A, Ma..
백준 12925번: Numbers www.acmicpc.net/problem/12925 12925번: Numbers 각 Test case에 대해, “Case #c: x”의 형식으로 각 줄에 정답을 출력한다. c는 Test Case의 번호이다. (1부터 매겨진다.) x는 해당 Test Case의 정답이다. www.acmicpc.net 다소 발상이 힘든 풀이를 가진 문제입니다. 우선 문제는 $M\leq \left ( 3+\sqrt{5} \right )^{n}\leq M+1$ 일 때 $M$ 의 $modulo$ 1000 값을 구하라는 것입니다. 가볍게 $n=1$ 인 상황부터 생각해봅시다. 계산기를 써보면 $\left ( 3+\sqrt{5} \right )^{1}=3+\sqrt{5}=5.236067\cdots$ 이므로, 정수부는 5가 됩니다. 그..
백준 18287번: 체스판 이동 www.acmicpc.net/problem/18287 18287번: 체스판 이동 크기가 N×M인 체스판이 있다. 체스판의 행 번호는 위에서부터 1, 2, ..., N이고, 열 번호는 왼쪽에서부터 1, 2, ..., M이다. 체스판의 각 칸은 (i, j)로 표현하고, i는 행 번호, j는 열 번호이다. 체스판의 www.acmicpc.net 우선 체스판이 어떻게 생겼는지 알아야 합니다. 검정색 칸을 $B$, 흰색 칸을 $W$라고 표현할 때 체스판의 생김새는 다음과 같습니다. $\begin{matrix}B & W & B & W & \cdots\\ W & B & W & B & \cdots\\ \vdots & \vdots & \vdots & \vdots & \ddots\end{matrix}$ $M$을 적당히 큰 ..

티스토리툴바