.png&blockId=3197e115-ee0d-4d9c-9f5d-4b57cb28634e)
피보나치수열
접근방법
1.
점화식을 찾는다.
a.
f(x) = f(x-1) + f(x-2)
2.
dp 테이블을 만들어 값들을 저장한다.
n = int(input())
def fibo(x):
dp = [0] * 91
if x == 1 or x == 2:
return 1
if dp[x] != 0:
return dp[x]
dp[x] = fibo(x-1) + fibo(x-2)
return dp[x]
Python
복사
n = int(input())
def fibo(x):
dp = [0] * 91
id[1], d[2] = 1, 1
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
return dp[x]
Python
복사
파도반 수열
접근방법
1.
점화식을 찾는다.
a.
f(x) = f(x-2) + f(x-3)
2.
dp 테이블을 만들어 값들을 저장한다.
n = int(input())
for i in range(n):
k = int(input())
dp = [1]*(k+1)
def sol(k):
# print(dp, '1')
for i in range(4, k+1):
dp[i] = dp[i-2] + dp[i-3]
# print(dp, '2')
return dp[k]
print(sol(k))
Python
복사
N으로 표현
접근방법
1.
N을 활용해서 numbers로 만들어야한다.
a.
n == numbers라면 1번만 사용하는 것.
2.
최솟값이 8보다 크면 -1을 리턴한다는 것
a.
for문 1개당 시간복잡도 O(8) = O(2^3)
3.
dp에 값을 담는다.
a.
숫자가 같은 값이 있을 필요가 없음 —> set활용하기
b.
dp에 set으로 담을 값들은, N이 cnt의 개수만큼 활용할 때, 나올 수 있는 값을 모두 담는다.
i.
set에서 들어갈 값은 n*cnt와 사칙연산한 값들이다.
def solution(N, number):
answer = 0
if N == number:
return 1
dp = []
# 최솟값이 8보다 크면 -1을 return 합니다.
for cnt in range(1, 9):
temp = set()
temp.add(int(str(N)*cnt)) #5, 55, 555
# print(set)
for i in range(1, cnt):
for first in dp[i-1]:#연산자 기준 앞에 오는 숫자
for second in dp[cnt-i-1]: #연산자 기준 뒤에 오는 숫자
# 연산 순서가 바뀌어도 동일
temp.add(first+second)
temp.add(first*second)
# 연산 순서가 바뀌면 달라짐
temp.add(first-second)
temp.add(second-first)
if first != 0:
temp.add(second//first)
if second != 0:
temp.add(first//second)
# print(f"dp={dp}")
if number in temp:
return cnt
dp.append(temp)
return -1
print(solution(5, 12))
Python
복사
도둑질
접근방법 1(실패)
1.
3개씩 끊어서 3개의 값중 큰 값을 방문처리한다.
2.
방문을 확인할 visited를 만든다.
a.
방문한 곳 뿐만 아니라, 방문으로 인해 경보가 울린 옆집들도 들어가지 못하기에 i-1, i, i+1 모두 false처리한다.
3.
dp에는 방문헀던 곳의 값을 담는다.
def solution(money):
dp = [0] * len(money)
visited = [True] * len(money)
# 방문하면 i-1, i+1 털지 못함
# 첫번째와 마지막집도 이웃??? ok
# 첫집을 무조건 터는 경우 vs 두번째집을 무조건 터는 경우
for i in range(len(money)-1):
if i == 0 :
max_num = max(money[-1], money[i], money[i+1])
max_index = money.index(max_num)
dp[max_index] = max_num
visited[-1], visited[i], visited[i+1] = False, False, False
if visited:
# print(f"i={i}, visited={visited}, dp={dp}, ago")
max_num = max(money[i-1], money[i], money[i+1])
max_index = money.index(max_num)
dp[max_index] = max_num
visited[max_index-1], visited[i], visited[i+1] = False, False, False
# print(f"i={i}, visited={visited}, dp={dp}, after")
answer = sum(dp)
return answer
Python
복사
차후에 첫집과 마지막집이 이어진다는 것을 알아차려서 if i== 0 부분 추가
이 방법도 문제를 정확성이 0임 —> reset
접근방법 2
1.
dp에 값을 쌓는 방식을 도전해봄
2.
첫집과 마지막집에 이어져있다면, 두 집중 한 곳은 무조건 방문할 수밖에 없음 (시작이 2가지 경우의 수)
a.
첫 집은 방문할 경우 —> 마지막집, 두번째집을 털지 못함
b.
두번째집을 방문할 경우 —> 마지막집은 방문하고, 첫번째집을 털지 못함
c.
dp 테이블을 두 개를 만든다. dp1, dp2
3.
dp테이블과 money리스트를 동시에 활용한다.
a.
dp에 집 방문으로 털었던 돈들의 최대값을 계속해서 누적해간다.
b.
dp[i-1]값과 dp[i-2]+money[i] 값을 비교해서 큰 값이 누적된 최대값이 된다.
def solution(money):
# 방문하면 i-1, i+1 털지 못함 --> dp값 누적
# 첫번째와 마지막집도 이웃??? ok
# 첫집을 무조건 터는 경우
dp1 = [0] * len(money)
dp1[0] = money[0]
dp1[1] = max(money[0], money[1])
for i in range(2, len(money)-1):
dp1[i] = max(dp1[i-1], dp1[i-2]+money[i])
# print(f"dp1={dp1}")
#두번째집을 무조건 터는 경우
dp2 = [0] * len(money)
dp2[1] = money[1]
for i in range(2, len(money)):
dp2[i] = max(dp2[i-1], dp2[i-2]+money[i])
# print(f"dp2={dp2}")
answer = max(max(dp1), max(dp2))
return answer
moeny = [1, 2, 3, 1]
print(solution(moeny))
Python
복사
