전체 글 (117) 썸네일형 리스트형 백준 11693번: n^m 의 약수의 합 https://www.acmicpc.net/problem/11693 11693번: n^m의 약수의 합 nm의 모든 약수의 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 소인수분해를 $O\left ( \sqrt{N} \right )$ 에 구현할 수 있으면 충분한 문제입니다. 즉, trial division이라 부르는 방법을 쓰면 충분합니다. 일반적으로 다음이 알려져있습니다. 자연수 $N$ 이 소수 $p_{1},p_{2},\cdots,p_{m}$ 에 의해 다음과 같이 소인수분해 될 때, $N=p_{1}^{\alpha_{1}}\times p_{2}^{\alpha_{2}}\times\cdots\times p_{m}^{\alpha_{m}}$ $\left ( 1 \right .. 백준 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가 됩니다. 그.. 이전 1 ··· 7 8 9 10 11 12 13 ··· 15 다음