이친수 (BOJ-2193)
in ALGORITHM
‘시간제한 2초, 메모리제한 128MB, BOJ-2193’
이친수 (BOJ-2193)
이 문제는 결과값, 과정 모두에서 점화식이 도출 가능하다. 그래서 해결하는데 10분도 걸리지 않았다.
결과값인 자릿수에 따른 이친수의 갯수로 해결하면 다음과 같다.
결과값들을 보면 자릿수가 n-2일때의 갯수와 n-1일때의 갯수를 합친 값이 자릿수 n의 이친수의 갯수라는걸 알 수 있다.
이를 구현하면 다음과 같다.
이친수의 갯수를 활용한 풀이🤞
n = int(input())
dp = [1, 1]
for i in range(2, n):
dp.append(dp[i - 2] + dp[i - 1])
print(dp[n - 1])
과정으로 자릿수 n에 따른 뒷자리에 1이 오는 경우의 수와 0이 오는 경우의 수를 구해 보면 다음과 같다.
여기서 n-2의 경우의 수 + n-1의 경우의 수가 n의 경우의 수라는 걸 알 수 있다.
초기값으로 n=1, n=2일때의 경우의 수를 초기화해준다.
그리고 3부터 dp를 n까지 초기화 해준다.
1과 0이 뒷자리에 오는 경우의 수를 활용한 풀이
n = int(input())
dp = [[0] * 2 for _ in range(91)]
dp[1][0] = 0
dp[1][1] = 1
dp[2][0] = 1
dp[2][1] = 0
for i in range(3, n + 1):
dp[i][0] = dp[i - 2][0] + dp[i - 1][0]
dp[i][1] = dp[i - 2][1] + dp[i - 1][1]
print(sum(dp[n]))
