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에 추가한다.

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

처음엔 무식하게 2중 for문으로 돌려보았다.
맞겠지 싶었는데 시간초과가 떴다.

이전의 반도체 설계 문제와 동일하게 최장 증가 수열을 구하는 문제다.

2020년 4원 7일 포스트 수정

저 문제 풀 때는 dp가 뭔지도 몰랐다.
이번엔 동적 계획법으로 풀어봤다.
dp[i]에 arr[i]이전의 값들을 비교하며 arr[i]보다 작은 값이 있다면 그 때의 dp[]에 담겨있는 값 + 1을 dp[i]에 넣는다. arr[i]이전의 모든 수에 위 과정을 반복했을 때 가장 큰 수가 dp[i]가 된다.
마지막으로 dp[]에 담겨있는 값 중 가장 큰 값이 최장증가수열의 길이가 된다.