백준/ Silver 5 문제 , 백준 파이썬 9625 , BABBA

백준/ Silver 5 문제 , 백준 파이썬 9625 , BABBA 

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
처음에는 문자열을 가지고 풀려고 했으나 값이 나중에 너무 커지게 되서 방법을 바꿨다.

 

<문제 출처>

 

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

9625번: BABBA

 

------------------------------------------------------------------------------------------------------------------------------

 

B => BA 로 바뀌고

 

A => B 로 바뀌는게 규칙이다.

 

이게 처음에는 문자길이가 크게 안변하지만 

 

나중에는 B 를 모두 BA 로 만들면 문자 길이가 팍팍 는다.

 

 

처음 주어진 A 를 카운트 해보면

 

1  0

 

그 다음 B 는

 

0  1

 

그 다음 BA는

 

1  1

 

그 다음 BAB는

 

1  2

 

그 다음 BABBA 는 

 

2  3

 

.

.

.

 

이런식인데 규칙이 보인다. 위에 두 값을 더하면 밑의 값이 된다.

 

이 규칙을 이용해서

 

[1,0]

   [0,1]

      [1,1]

         [1,2]

            [2,3]

              .    

              .

              .

 

이런 식으로 계산해주면된다.

 

 

참고로 최댓값 45를 입력해주면

 

701408733 1134903170   이런 큰 수가 출력되게 된다.

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답