S3 1904. 01타일

문제 보기 :  1904번: 01타일

---

문제

• 정답률 : 31%

---

작성 코드 & 풀이 해설

from itertools import permutations, combinations_with_replacement

# 가능한 타일 조합 (00, 1)
arr = ['00', '1']

# 입력: 문자열의 길이
str_length = int(input())

# 가능한 결과를 저장할 집합 (중복 제거를 위해 set 사용)
answer = set()

# 1부터 str_length까지 조합의 길이를 증가시켜가며 처리
for n in range(1, str_length + 1):
    # arr에서 중복 조합 생성 (길이가 n인 조합)
    for ls in combinations_with_replacement(arr, n):
        # 생성된 조합에 대해 순열 생성
        for p_ls in set(permutations(ls)):
            # 순열을 문자열로 변환
            p_ls = ''.join(p_ls)
            # 문자열 길이가 str_length인 경우만 추가
            if len(p_ls) == str_length:
                answer.add(p_ls)

# 가능한 조합의 개수를 15746으로 나눈 나머지 출력
print(len(answer) % 15746)

처음 사용한 방법은 “조합과 순열”을 사용하는 방법이었다.

먼저, 중복 조합(combinations_with_replacement)으로 길이가 1부터 str_length까지 가능한 조합을 만든다.

그리고 각 조합에 대해 순열(permutations)을 생성해 순서를 바꾼 경우를 확인한다.

이후에는 길이가 str_length인 문자열만을 선택해 집합에 추가한다.

최종적으로 가능한 조합의 개수를 출력하며, 결과를 15746으로 나눈 나머지를 출력했다.

근데 이렇게 풀이하면 계산량이 많아서 시간 초과가 발생했고, 케이스 별로 몇개의 2진 문자열이 발생하는지 계산해보았다.

1- 1 {'1'}
2- 2 {'00', '11'}
3- 3 {'100', '001', '111'}
4- 5 {'1100', '0011', '1111', '1001', '0000'}
5- 8 {'00111', '10011', '00100', '11001', '00001', '11100', '11111', '10000'}
6- 13 {'100100', '111001', '001111', '100111', '001100', '111111', '111100', '001001', '100001', '000000', '000011', '110011', '110000'}

이렇게 피보나치 수열로 구할 수 있는 것을 확인할 수 있었고, 이에 맞게 코드를 변형했다.

# 입력: 문자열 길이
str_length = int(input())

# DP 테이블 초기화 (0부터 str_length까지 저장)
lst = [0] * (str_length + 1)

# 문자열 길이가 1일 때, 경우의 수는 1 (1)
if str_length >= 1:
    lst[1] = 1

# 문자열 길이가 2일 때, 경우의 수는 2 (11, 00)
if str_length >= 2:
    lst[2] = 2

# 문자열 길이가 3 이상일 때, 경우의 수 계산
for i in range(3, str_length + 1):
    # 점화식: F(n) = F(n-1) + F(n-2), 결과를 15746으로 나눈 나머지 저장
    lst[i] = (lst[i-1] + lst[i-2]) % 15746

# 최종적으로 구한 경우의 수 출력
print(lst[-1])

점화식은 F(n) = F(n-1) + F(n-2)로 정의할 수 있었고, 이 값을 효율적으로 계산하기 위해 결과를 15746으로 나눈 나머지만 저장했다.

결과적으로 길이가 str_length인 2진 문자열의 가능한 경우의 수를 출력하며 마무리했다.