프로그래머스 Lv2 DP 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.
문제
https://school.programmers.co.kr/learn/courses/30/lessons/12914
[나의 풀이]
⌛ 시간초과 (31/100 점)
def solution(n):
from collections import deque
answer = 0
queue = deque([0])
while queue:
v = queue.popleft()
if v>n:
continue
elif v<n:
queue.append(v+1)
queue.append(v+2)
else:
answer += 1
return answer%1234567
주어진 입력값 n을 1 혹은 2만으로 더할 수 있는 케이스를 구하는 문제입니다. 이를 구현하기 위해 BFS로 n보다 작을 시에 1 혹은 2를 더한 케이스를 추가하며 모든 경우의 수를 구하였지만 다수 케이스에서 시간초과가 발생하여 다른 풀이를 참고하였습니다.🐻🐻🐻
[다른사람의 풀이1]
def solution(n):
if n<3:
return n
d=[0]*(n+1)
d[1]=1
d[2]=2
for i in range(3,n+1):
d[i]=d[i-1]+d[i-2]
return d[n]%1234567
DP로 해결가능한 문제였습니다.
n=1이면 [1], n=2이면 [1,1]/[2]인 경우로 해결이 가능합니다. 이를 기반으로 n=3인 경우를 구한다면 n=1일때의 경우에서 +2만 하면 되고, 또한 n=2인 경우에 +1만 하면되기 때문에 n=1,n=2인 경우의 수를 더하면 됩니다. 그리하여 DP로 피보나치 수열을 구하듯이 입력값 n을 완성하는 케이스를 n-1,n-2 케이스의 합을 구하는 방식을 구현할 수 있습니다.🐻❄️🐻❄️🐻❄️
[다른사람의 풀이2]
def solution(n):
# n=1 일 때 1 반환
if n == 1: return 1
else:
# DP 테이블 초기화
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 2
# 점화식 적용, 숫자가 커지는 것을 방지하기 위해
# 계속해서 나머지 연산자 활용하기
for i in range(3,n+1):
dp[i] = (dp[i-2] + dp[i-1]) % 1234567
# DP 테이블 마지막 값 반환
return dp[-1]
이외 다른 풀이도 동적프로그래밍으로 해결한 방법이였습니다.🐼🐼🐼
감사합니다.