[백준] 2193번 (python 파이썬)

https://www.acmicpc.net/problem/2193

2193번: 이친수

 

• 부분 반복 구조 : 위의 그림과 같음
• 최적 부분 구조 : n일때 최적의 값을 가지기 위해선 n-1일때 최적의 값을 가져야 한다. (애초에 여러값을 가질 수 없는 문제이다)
• 메모이제이션 : 입력받는 n보다 1 더 크게 배열을 만들어 놓는다. n값과 인덱스를 맞추기 위함이다.
• 접근 방식 : n이 1일때의 값을 알고 있으므로 bottom - up 으로 접근하기가 쉽다.

n = int(input())

cache = [[0 for _ in range(2)] for _ in range(n+1)]
cache[1] = [0, 1]
for i in range(2, n+1):
  cache[i][0] = sum(cache[i-1])
  cache[i][1] = cache[i-1][0]
print(sum(cache[n]))

 

아래는 top - down 방식으로 푼 코드이다.

n = int(input())
cache = [None for _ in range(n+1)]

def get_cache(n):
  if cache[n]:
    return cache[n]
  elif n == 1:
    cache[1] = [0, 1]
  else:
    cache[n] = [sum(get_cache(n-1)), get_cache(n-1)[0]]
  return cache[n]
print(sum(get_cache(n)))

 

bottom - up 방식과 다른점은 cache 리스트를 초기화 할때 bottom - up 방식은 [0, 0] 으로 초기화 한것에 비해

top - down 방식은 None으로 초기화 했다.

이는 cache[n] 이 존재하는지 검사를 위해서이다.

[0, 0]은 아직 값을 할당하지 않은 상태이다. 

if cache[n] 의 의미는 cache[n]이 값이 존재하면 if문의 바디로 들어가는 것인데

cache[n] 가 [0, 0]이면 값이 존재한다고 판단하기 때문에 [0, 0]으로 초기화 하는 대신 None으로 초기화 했다.