2n 크기의 직사각형은 2(n-1)크기의 직사각형에서 세로로 길쭉한 블럭 하나를 추가한 것과 같고 2(n-2)크기의 직사각형에서 가로로 길쭉한 블럭 두개를 쌓아서 추가하는 경우와 같다.
2(n-2)크기의 직사각형 역시 세로로 길쭉한 블럭을 두개 추가하면 2n크기인 직사각형이 되지만, 2(n-1)와 겹치는 경우가 발생하기에 제외한다.

시간 제한이 0.25초로 걸려있는 것이 정직하게 피보나치 돌리면 시간 초과가 뜬다는 것을 암시한 것인가.

dp[i]에는 정수 i를 1, 2, 3의 합으로 나타내는 방법의 수가 담겨있다.
그래서 정수 5를 1, 2, 3의 합으로 나타내는 방법의 수가 궁금하다면, dp[2] + dp[3] + dp[4]가 될 것이다.

크게 두 가지 경우의 수가 있다.

1. 3로 나누어 떨어질 경우
2. 3으로 나누어 떨어질 경우

3번 조건은 언제나 적용할 수 있기 때문에 처음부터 계산하고 시작한다.
2와 3의 공배수 같은 경우는 2와 3 둘 다 나누어 떨어지기 때문에 다른 조건을 만들어야 하나 싶었지만 어차피 dp[]에 저장된 값을 같은 i를 돌고 있을 때 다시 확인하므로 상관이 없다.

우선 한 면이 바닥에 가려져 있으므로 총 5n^2만큼의 면을 볼 수 있다.
그 중 3면이 보이는 주사위는 윗쪽 꼭지점 4개, 2면이 보이는 주사위는 눈에 보이는 모서리 8개와 아랫쪽 꼭지점 4개, 1면이 보이는 주사위는 5n^2 - (3 * 3면이 보이는 주사위의 수) - (2 * 2면이 보이는 주사위의 수) 이다.
이를 식으로 나타내면,

3 면 == 4 개
2 면 == 8n - 12 개
1 면 == 5n^2 - 16n + 12 개

로 정리할 수 있다.

사전순이기 때문에 A, C, G, T 순으로 세로줄에 등장하는 갯수가 제일 많은 뉴클레오타이드로 배치한다.
Hamming Distance는 세로줄에서 선택된 뉴클레오타이드를 제외하고 나머지 뉴클레오타이드의 등장횟수를 세면 된다.

보자마자 스택이 떠올랐다.
물론 스택을 사용하지는 않았다.
한 글자씩 받아와서 ‘X’ 4개가 쌓일 때, ‘.’을 만날 때, 모두 읽어서 종료됐을 때의 경우에서 최종 str에 추가해주는 방식으로 풀었다.


‘.’을 만났을 때와 종료됐을 때 종료조건과 2개가 쌓였을 때 “BB”를 str에 추가한다.

유클리드 호제법은 2개의 자연수 사이의 최대공약수를 구할 때 사용하는 알고리즘이다.


2개의 자연수 a, b(a > b)가 있고 a % b = r 이라고 한다면 a, b의 최대공약수는 a, r의 최대공약수와 같다. 이 성질을 이용해 b를 r로 나눈 나머지 r’을 구하고 다시 r을 r’으로 나눈 나머지를 구하는 과정을 반복해서 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수라고 한다.

읽히는 대로 짜면 된다.
신기한 점은 이 문제의 정답은 1, 3, 4, 12, 20, 60으로 6가지 밖에 없다.
0부터 99까지의 숫자 중에 정답이 1인 숫자가 1개, 3인 숫자가 3개 4인 숫자가 4개, 5인 숫자가 5개, 12인 숫자가 12개, 20인 숫자가 20개, 60인 숫자가 60개다.
각 정답이 같은 숫자끼리 돌아가며 등장한다.

자연수의 집합에서 소수를 찾아내는 방법으로 모든 수를 나눠보며 나머지를 확인하는 방법보다 빠르기 때문에 유용하게 사용된다.