BOJ 1904.01타일

moong·2021년 7월 31일

알고리즘

목록 보기

4/5

난이도가 높진 않지만, 기계적으로 문제를 풀던 나에게 생각할 거리를 많이 던져줬다.

문제

00카드와 1카드를 활용하여, N이 주어졌을 때 만들 수 있는 모든 가짓수를 세는 것
예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.
단 타일들은 무한히 많은 것으로 가정하자.
1 ≤ N ≤ 1,000,000
출력: 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지

해결

DP를 활용하여 풀긴 했지만, 여러 문제점에 봉착했다.
점화식, 메모리 초과, (개선방안) swap 활용

1. 점화식

N에 값을 대입하여 적다보면 피보나치와 동일한 점화식임을 알 수 있다. 하지만 증명한 것이 아니라 대입에 의한 결과값을 보고 추측한 것이라 찝찝했다.
적다보면 N이 짝수인 경우, 길이가 이전 짝수값(N-2)일 때 결과물에 00을, 길이가 이전 홀수값(N-1)일 때 결과물에 1을 더해주면 된다는 것을 알 수 있다.
N이 홀수인 경우도 비슷하다. N-2일 때 결과물에 1을, N-1일 때 결과물에 00을 더해주면 된다.
따라서, a(n) = a(n-1) + a(n-2)이라는 점화식을 믿고 사용할 수 있다.

2. 메모리 초과

N = int(input())
counts = [0] * 1000001
counts[1], counts[2] = 1, 2
for i in range(3, N+1):
    counts[i] = counts[i-1] + counts[i-2]
print(counts[N]%15746)

왜 15746으로 나눈 나머지를 출력하라는 건지 몰랐는데 N값 때문이었다.
N의 최대값은 100만이기 때문에 메모리를 많이 잡아먹는다.
따라서 배열에 결과값을 저장할 때부터 15746으로 나눈 나머지를 저장해야 한다.

for i in range(3, N+1):
    counts[i] = (counts[i-1] + counts[i-2]) % 15746
print(counts[N])

3. SWAP

N이 100만이라면 100만+1개의 배열이 만들어진다.
이것도 메모리를 많이 잡아먹는 것 같은데 swap으로 해결할 수 있다.
이 문제는 테스트케이스 수를 입력받지 않기 때문에, 다음에 주어질 수가 배열에 값을 가지고 있는지 확인하지 않는다.
따라서 이전 결과값과 전전 결과값만 알고 있으면 된다.

N = int(input())
if N == 1:
    res = 1
elif N == 2:
    res = 2
else:
    a, b = 1, 2
    for i in range(3, N+1):
        a, b = b, (a+b) % 15746
        res = b
print(res)