백준 14860번: GCD 곱
https://www.acmicpc.net/problem/14860 14860번: GCD 곱 N과 M 이 주어졌을 때, GCD(1, 1) × GCD(1, 2) × ... × GCD(1, M) × GCD(2, 1) × GCD(2, 2) × ... × GCD(2, M) × ... × GCD(N, 1) × GCD(N, 2) × ... × GCD(N, M)을 구하는 프로그램을 작성하시오. www.acmicpc.net $GCD\left ( 1,1 \right)\times \cdots \times GCD\left ( N,M \right)$ 을 구하는 문제입니다. $N\;,\;M$ 의 범위를 살펴보니, 위 식을 소인수분해하는 게 가능할 것 같습니다. 그러면 eratosthenes' sieve로 15000000 이하의..
백준 3827번: 일차원 세포 자동자
https://www.acmicpc.net/problem/3827 3827번: 일차원 세포 자동자 각 테스트 케이스에 대해서, 시간 T에서 세포의 상태를 출력한다. 출력은 다음과 같은 형식이다. S(0,T) S(1,T) ... S(N-1,T) 각 세포의 상태는 정수이고, 공백으로 구분되어야 한다. www.acmicpc.net 지문에서 설명하는 점화식을 그대로 행렬로 표현해주면 됩니다. $S\left( i,t+1 \right)=A\times S\left( i-1,t \right)+B\times S\left( i,t \right)+C\times S\left( i+1,t \right)$ 이 점화식에서 $i=0$ 일 때, $i=N-1$ 일 때만 잠시 생각해보면, $S\left( 0,t+1 \right)=B\ti..
백준 13976번: 타일 채우기 2
https://www.acmicpc.net/problem/13976 13976번: 타일 채우기 2 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000,000,000,000)이 주어진다. www.acmicpc.net 타일 채우기라고 부르는 유형은 풀이법이 어느정도는 정해져 있습니다. 보통 점화식을 구해야하는데, 그 과정에서, 다음 과정을 거칩니다. 작은 $N$ 값에 대해 답을 구해봅니다 적당히 큰 값의 $X$ 에 대해서, 가로로 $X$ 만큼의 크기(이 문제에서는 $3\;by\;X$ )를 얻었다고 칩니다 그 다음 $X+1$ , $X+2$ , 로 확장해가면서 점화식을 추론합니다 이 글에서도 위와 같은 과정을 거칠 것입니다. 우선 $N=2$ 일 때, 답은 3입니다. 다음과 같은 경우의 수가 있습니다. $N=4..