문제 설명
•
길이가 인 2진 수열을 만들 때, 사용 가능한 타일이 1과 00만 있을 경우 만들 수 있는 모든 수열의 가짓수를 구하는 문제
예제 입력/출력
•
입력1
4
Plain Text
복사
•
출력1
5
Plain Text
복사
제약 조건
•
문제 풀이
•
접근1 브루트 포스 (완전 탐색) -
◦
일 때 가능한 모든 경우를 생각해보면 각 노드에서 두 개의 선택(1 또는 00)이 가능하므로 최악의 경우 매 단계마다 2배로 경우의 수가 늘어난다.
▪
(숫자) → 남은 길이
◦
즉, 트리의 깊이가 이 되고 총 경우의 수는 이 된다.
•
접근2 DP -
◦
완전 탐색 과정에서 불필요한 연산을 줄이기 위해 동적 계획법(DP)을 사용하면 문제를 해결할 수 있다.
▪
길이 N의 2진 수열을 만들 때, 마지막에 놓을 수 있는 경우는 다음 두 가지뿐이다.
1.
1을 마지막에 놓은 경우 → 길이 N-1에서 가능한 경우의 수와 동일함
2.
00을 마지막에 놓은 경우 → 길이 N-2에서 가능한 경우의 수와 동일함
Q. 두 개의 1타일이 연속으로 오는 경우를 왜 고려하지 않나요?
점화식으로 이미 1을 연속으로 놓는 모든 경우를 포함하고 있다.
예를 들어, 111이라는 수열은 N=1에서 1을 두 번 추가하거나, N=2에서 1을 추가하는 방법으로 만들어진다.
즉, 점화식을 사용하면 자연스럽게 연속된 1이 포함되므로, 별도로 1을 연속해서 놓는 경우를 고려할 필요가 없다.
◦
DP 테이블 정의
▪
: 길이가 N인 2진 수열 중에서 지원이가 만들 수 있는 경우의 수
◦
DP 관계식
▪
◦
초기값 처리
▪
→ 1 하나만 가능
▪
→ 11, 00 두 가지 가능
풀이 코드
•
DP (1차원 배열 사용 O) -
import sys
input = lambda: sys.stdin.readline()
def count_binary_sequences(N):
if N == 1:
return 1
if N == 2:
return 2
dp = [0] * (N + 1)
dp[1], dp[2] = 1, 2
for n in range(3, N + 1):
dp[n] = (dp[n - 2] + dp[n - 1]) % 15746
return dp[N]
# 입력 값 받기
N = int(input())
print(count_binary_sequences(N))
Python
복사
•
DP (1차원 배열 사용 X) -
◦
위 코드는 O(N) 크기의 배열을 사용하지만, 사실 이전 두 개의 값만 유지하면 된다.
◦
배열을 사용하지 않고 O(1) 공간을 사용해서 문제를 풀면 메모리 사용과 연산 시간을 약 50% 개선할 수 있다!
import sys
input = lambda: sys.stdin.readline()
def count_binary_sequences(N):
if N == 1:
return 1
if N == 2:
return 2
prev1, prev2 = 1, 2
for _ in range(3, N + 1):
cur = (prev1 + prev2) % 15746
prev1, prev2 = prev2, cur
return prev2
# 입력 값 받기
N = int(input())
print(count_binary_sequences(N))
Python
복사