[JAVA] 백준 문제풀이(9625번 : BABBA)

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

9625번: BABBA

 

풀고나서 무슨 문제인가 싶어서 검색해보니 DP(다이나믹 프로그래밍)이라 그러는데

사실 문제풀때는 그냥 문제설명보고 직접 적어보면서 풀었읍니다..

문제 출제의도랑은 부합하지 않을 수 있읍니다

 

입력	0(초기)	1	2	3	4	5	6
출력	A	B	BA	BAB	BABBA	?	?
A(개수)	1	0	1	1	2	3	5
B(개수	0	1	1	2	3	5	8

 

일단 출력은 잘 모르겠고

 

입력 차수별 A개수, B개수를 보면

 

A개수 = 이전 차수의 B의 개수

B개수 = 이전 차수의 A+B

 

임을 알 수 있었습니다.

 

 

코드 설명

13~14

입력한 k의 입력만큼의 길이를 가진 배열을 선언

 

16~17

배열은 선언하고 값을 할당하던지 초기화를 하던지 해야합니다.

그런데 이후에 있을 반복문에서 초기화가 안되어있는 배열을 돌리면 오류가 나니 미리 알고 있는 초기 값을 지정합니다.

A가 0(초기), 1일때 개수

B가 0(초기), 1일때 개수

 

19~22

이미 각 배열 0~1을 직접 할당해줬으니 시작은 2로 합니다.

입력한 k(input)까지 반복문을 돌리게 합니다.

 

위에서 말했듯이

A는 이전 차수 B의 개수를 따라가고

B는 이전 차수의 A+B개수를 따라갑니다.