<aside> 🔥 백준 5705번 문제

</aside>

<aside> 🔥 문제 정리

위 그림과 같이 항상 웃는 얼굴에서 시작해서 인접한 길로만 이동해서 갈 수 있는 모든 경로를 출력.

</aside>

<aside> 🔥 접근 방법

다이나믹 프로그래밍을 배우기 전에 미리 연습하라고 출제해주신 문제인것같다.

처음에는 무슨 트리로 연결해야하는건지, 플로이드 워셜을 사용해야하는건지 도무지 감이 안잡혔다.

이럴때에는 그냥 무식하게 하나씩 그려보는게 좋을거 같아서 규칙을 찾아보려고 30분동안 그려봤다.

한참동안 그리다가 아래와 같은 경우의 수를 찾게 되었다. 1과 2는 그대로 자신의 수를 리턴해주고,

3일때부터는 전값 + 전전값의 규칙을 발견했다. 따라서 n일경우에는 아래 공식을 찾았다.

n -> n-1 값 + n-2 값

1. 1일때는 경우의 수는 1이다.
2. 2일때의 경우의 수는 2이다.
3. 3일때의 경우의 수는 3이다.
4. 4일떄의 경우의 수는 5이다.
5. 5일때의 경우의 수는 8이다. </aside>

<aside> 🔥 코드 진행

1. 입력값 받아주기

   0일때에는 종료하도록 한다.

   def input():
       return sys.stdin.readline().strip()
   
   while True:
       n = int(input())
       if n == 0:
           break
   

2. 결과를 추가할 딕셔너리를 생성해줬는데 키가 없어도 자동 생성 되도록 defaultdict()를 사용.

   q를 생성해서 1부터 시작하도록 해줬다.

   
   # 키가 없어도 자동으로 추가되는 defaultdict 사용
       result = collections.defaultdict()
   
       q = []  # q 생성
       q.append(1)  # 1부터 시작
   

3. q에 값이 있는동안 반복되도록 해서 종료 지점은 현재 큐에서 꺼낸 값이 n보다 커질때로 설정

   위에서 찾은 규칙을 적용했다.

   while q:  # q 반복
           cur = q.pop()  # q에서 현재값 뽑기
           if cur > n:  # cur이 입력값 n보다 커지면 종료
               break
   
           # 규칙을 찾았다!
           # 1일때는 어차피 1밖에 없다 -> 1개
           # 2일때 (1,2) (2) -> 2개
           # 3일때 (1,3) (1,2,3) (2,3) -> 3개
           # 4일때 (1,2,3,4) (1,3,4) (1,2,4) (2,3,4) (2,4) -> 5개
           # 5일때 (1,2,3,4,5) (1,2,3,5) (1,2,4,5) (1,3,4,5) (2,3,4,5) ... (2,3,5) -> 8개
           # 3일때부터 1로갈때 경우의수 + 2로갈때 경우의수
           # 4는 2로갈때 경우의수 + 3으로갈때 경우의수
   
           if cur == 1:  # 1일때
               result[cur] = 1
               q.append(cur + 1)
   
           elif cur == 2:  # 2일때
               result[cur] = 2
               q.append(cur + 1)
   
           # 3부터는 전전값 + 전값
           else:
               result[cur] = result[cur - 2] + result[cur - 1]
               q.append(cur + 1)
   

</aside>

<aside> 🔥 결과

다행히 런타임이나 메모리 관련 불합격이 되질 않았다.

오늘 수업이 다이나믹 프로그래밍이였는데, 이게 피보나치 수열이랑 똑같은 문제라는게 놀랍다.

</aside>