백준 1904 01타일 Python 풀이

🔷 백준 1904 01타일 Python 풀이

✅ 문제설명

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨습니다. 이 타일들은 각각 0 또는 1이 쓰여 있는 낱장의 타일입니다.

어느 날 짓궂은 동주가 장난을 쳐서 0이 적힌 타일 두 장을 붙여서 하나의 \($00$\) 타일을 만들었습니다. 결국 사용할 수 있는 타일은 다음 두 가지뿐입니다.

• 1이 적힌 낱장 타일 (길이 1짜리)
• 0이 적힌 낱장 두 장이 붙어 있는 \($00$\) 타일 (길이 2짜리)

지원이는 이 두 가지 타일을 사용하여 길이가 \(N\)인 2진 수열을 만들고자 합니다. 예를 들어 \(N=1\)이라면 \(1\)만 가능합니다. \(N=2\)라면 \(11\)과 \(00\) 두 가지가 가능합니다. \(N=4\)라면 \(0011\), \(0000\), \(1001\), \(1100\), \(1111\) 등 총 5가지 수열이 가능합니다.

길이 \(N\)이 주어졌을 때, 지원이가 만들 수 있는 2진 수열의 가짓수를 \(15746\)으로 나눈 나머지를 구하세요.

제한 조건

• \(1 \leq N \leq 1,000,000\)

테스트케이스

입력 예시 1

4

출력 예시 1

5

설명

길이가 \(N\)인 경우의 수를 직접 세어 보면서 작은 수부터 살펴보겠습니다.

• \(N=1\)
  • 만들 수 있는 수열: 1
  • 총 1가지
• \(N=2\)
  • 만들 수 있는 수열: 11, 00
  • 총 2가지
• \(N=3\)
  • 만들 수 있는 수열: 111, 001, 100
  • 총 3가지
• \(N=4\)
  • 만들 수 있는 수열: 1111, 0011, 1001, 1100, 0000
  • 총 5가지
• \(N=5\)
  • 만들 수 있는 수열: 11111, 00111, 10011, 11100, 00100, 10001, 00001, 00011
  • 총 8가지

여기서 규칙이 보입니다.

• \(N=1\): 1
• \(N=2\): 2
• \(N=3\): 3
• \(N=4\): 5
• \(N=5\): 8

앞선 두 항의 합이 다음 항이 됩니다.

💡 아이디어

길이가 \(N\)인 수열을 만들기 위해서는, \(N\)이 1이거나 2인 경우를 제외하면 항상 두 가지 선택지를 가집니다.

• \(N-1\) 길이의 수열 뒤에 길이가 1인 1 타일을 붙입니다.
• \(N-2\) 길이의 수열 뒤에 길이가 2인 00 타일을 붙입니다.

이 두 가지 선택을 더해주면 \(N\)길이의 경우의 수가 완성됩니다.

즉, 점화식:

$$dp[N] = dp[N-1] + dp[N-2]$$

작은 값에서의 과정

\(N=1\)일 때

• 길이가 1인 경우의 수: 1
• 총 \(1\)가지 → \(dp[1]=1\)

\(N=2\)일 때

• \(N-1=1\)인 수열 뒤에 1을 붙이면: 11
• \(N-2=0\)인 수열 뒤에 00을 붙이면: 00 (여기서 \(dp[0]=1\)로 간주)
• 총 \(2\)가지 → \(dp[2]=2\)

\(N=3\)을 \(N=2\)와 \(N=1\)에서 만드는 과정

$$dp[3] = dp[2] + dp[1]$$

• \(dp[2]=2\)를 선택하고 그 뒤에 1을 붙이면:
  • 11+1 = 111
  • 00+1 = 001
  이렇게 2가지
• \(dp[1]=1\)을 선택하고 그 뒤에 00을 붙이면:
  • 1+00 = 100
  이렇게 1가지

총 \(3\)가지 → \(dp[3]=3\)

여기서 \(N=3\)은 홀수이지만, \(dp[3]\) 계산에서 \(dp[2]\)와 \(dp[1]\)이 이미 각각 1과 00을 적절히 배치하는 경우를 모두 고려합니다. 즉, 홀수라서 특정한 규칙이 생기는 게 아니라 점화식으로 모든 선택을 자동으로 포함합니다.

\(N=4\)를 \(N=3\)과 \(N=2\)에서 만드는 과정

$$dp[4] = dp[3] + dp[2]$$

• \(dp[3]=3\)을 선택하고 그 뒤에 1을 붙이면:
  • 111+1 = 1111
  • 001+1 = 0011
  • 100+1 = 1001
  이렇게 3가지
• \(dp[2]=2\)를 선택하고 그 뒤에 00을 붙이면:
  • 11+00 = 1100
  • 00+00 = 0000
  이렇게 2가지

총 \(5\)가지 → \(dp[4]=5\)

여기서 \(N=4\)는 짝수입니다. 그런데도 마찬가지로 두 가지 선택(\(dp[3]\)과 \(dp[2]\))을 더하면 모든 경우를 빠짐없이 계산합니다. 즉, 짝수라서 특별히 다르게 계산할 필요는 없습니다.

\(N=5\)를 \(N=4\)와 \(N=3\)에서 만드는 과정

$$dp[5] = dp[4] + dp[3]$$

• \(dp[4]=5\)를 선택하고 그 뒤에 1을 붙이면:
  • 1111+1 = 11111
  • 0011+1 = 00111
  • 1001+1 = 10011
  • 1100+1 = 11001
  • 0000+1 = 00001
  이렇게 5가지
• \(dp[3]=3\)를 선택하고 그 뒤에 00을 붙이면:
  • 111+00 = 11100
  • 001+00 = 00100
  • 100+00 = 10000
  이렇게 3가지

총 \(8\)가지 → \(dp[5]=8\)

여기서도 \(N=5\)는 홀수지만, 점화식 안에서 \(N-1\)과 \(N-2\)를 더하는 과정만으로 모든 경우를 세게 됩니다.

왜 순서를 무시하지 않아도 되는가

예를 들어 \(N=3\)일 때,

• 100
• 001

이 두 수열은 서로 다른 이유가 있습니다. 왼쪽부터 채우는 순서에 따라 만들어진 모양이 달라지기 때문입니다. 점화식은 이미 왼쪽부터 순서대로 채워 나간 경우를 모두 세어주므로, 방향을 명시적으로 구분하거나 추가로 계산할 필요는 없습니다.

즉, \(dp[N-1]\)의 모든 경우는 \(N-1\)칸이 왼쪽부터 채워진 모든 가능한 수열을 나타내고, 그 뒤에 1을 붙이면 \(N\)이 됩니다. \(dp[N-2]\)도 마찬가지로 왼쪽 \(N-2\)칸을 채운 뒤 00을 붙입니다.

따라서 왼쪽에 1을 붙인 경우와 왼쪽에 00을 붙인 경우가 서로 다른 경우라는 점이 점화식 안에 이미 포함되어 있습니다.

핵심 요약

• \(N=3\) → \(dp[2]+dp[1] = 2+1=3\), 과정: 111, 001, 100
• \(N=4\) → \(dp[3]+dp[2] = 3+2=5\), 과정: 1111, 0011, 1001, 1100, 0000
• \(N=5\) → \(dp[4]+dp[3] = 5+3=8\), 과정: 위에서 나열한 8가지

이렇게 매번 \(N-1\)과 \(N-2\)의 경우를 더해주면, 왼쪽에 어떤 타일을 붙이느냐에 따라 생기는 모든 가능한 수열이 모두 포함됩니다. 홀수든 짝수든 따로 구분할 필요가 없고, 점화식으로 계산하면 됩니다.

💻 전체코드

N=int(input())
dp=[]

dp.append(1)
dp.append(2)

for i in range(2,N):
    dp.append((dp[i-2]+dp[i-1])%15746)

print(dp[N-1])

📝 개별코드 설명

• `N=int(input())`
  사용자로부터 정수 \(N\)을 입력받아 변수 `N`에 저장합니다.
• `dp=[]`
  동적 프로그래밍 값을 저장할 리스트 `dp`를 초기화합니다.
• `dp.append(1)`
  `dp.append(2)`
  문제에서 주어진 초기 조건에 따라 길이가 \(1\)인 경우의 수 \(1\)과 길이가 \(2\)인 경우의 수 \(2\)를 `dp` 리스트에 추가합니다. 이는 점화식 계산의 기초가 됩니다.
• `for i in range(2,N):`
  길이가 \(3\) 이상인 경우부터 \(N\)까지의 값을 계산하기 위해 반복문을 시작합니다. Python 리스트의 인덱스는 0부터 시작하므로, `dp[i]`가 \(i+1\) 길이에 해당합니다. 따라서 길이가 3인 경우(인덱스 2)부터 계산합니다.
• `dp.append((dp[i-2]+dp[i-1])%15746)`
  이전에 설명된 점화식 \(dp[N] = dp[N-1] + dp[N-2]\)에 따라 현재 길이에 대한 경우의 수를 계산합니다. `dp[i-2]`는 \(i-1\) 길이의 경우의 수, `dp[i-1]`은 \(i\) 길이의 경우의 수를 나타냅니다. 계산된 값에 \(15746\)으로 나눈 나머지를 저장하여 오버플로우를 방지합니다.
• `print(dp[N-1])`
  최종적으로 계산된 길이 \(N\)에 해당하는 경우의 수(`dp[N-1]`)를 출력합니다. (Python 리스트는 0부터 인덱싱되므로, \(N\)번째 값은 `N-1` 인덱스에 저장됩니다.)

✨ 결론

• 길이가 \(N\)인 2진 수열을 만들 수 있는 경우의 수는 점화식 \(dp[N]=dp[N-1]+dp[N-2]\)로 구할 수 있습니다.
• 매번 계산마다 \(15746\)으로 모듈러 연산을 해줘야 오버플로를 방지할 수 있습니다.
• 초기값 \(dp[1]=1\), \(dp[2]=2\)를 반드시 설정해야 합니다. (파이썬 리스트에서는 `dp.append(1)`, `dp.append(2)`로 초기화됩니다.)
• 방향을 고려하지 않고 왼쪽부터 채우는 모든 경우를 자연스럽게 포함하기 때문에 점화식만으로 충분히 계산됩니다.