[BOJ_9625] BABBA

 

📌 문제 링크: https://www.acmicpc.net/problem/9625

9625번: BABBA

 

✅ 내 풀이(Success) :

 

🧐 Review:

  버튼을 누르지 않았을 때(dp 배열의 0번째 원소)는 A의 개수는 1이고, 버튼을 한 번 눌렀을 때(dp 배열의 1번째 원소)는 A의 개수는 0이 되고, B의 개수는 1이 된다. 2번째 원소부터 그 이전 두 개의 항의 원소의 값을 더해 A와 B의 개수를 구할 수 있다. 처음에는 'A'와 'B'를 이용해 문자열을 직접 더하고 dp 배열의 원소를 수정하는 방식으로 코드를 작성했는데, 코드를 제출해보니 메모리가 초과하는 상황이 발생했다. 그래서 문자열을 직접 더하는 방법보다 원소의 개수를 이용하는 방법이 떠올라 코드를 위의 코드와 같이 수정하고 제출했더니 문제를 해결할 수 있었다.

 

🚩 Idea:

 1. dp문제로 경우의 수를 나열해보면서 규칙성을 찾는다.

 2. 규칙성을 이용해 점화식을 세운다.