[Programmers] 안티세포

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/86054

프로그래머스

 

a의 길이가 최대 20만이기 때문에 DP로 접근해야 하는 문제였습니다.

늦잠님 블로그 글을 참고하여 풀었습니다.

https://velog.io/@woolzam/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Lv.4Java-%EC%95%88%ED%8B%B0%EC%84%B8%ED%8F%AC

[프로그래머스/Lv.4][Java][C++] 안티세포

 

알고리즘은 다음과 같습니다.

1. 각 b 배열 (세그먼트)의 각 원소는 초기에는 개별 안티 세포로 존재하며, 아무 합성도 진행되지 않은 상태이므로 경우의 수는 1입니다.

 

2. 합성 선택 과정은 다음과 같습니다. (connect 함수)

• 현재 셀과 그 바로 왼쪽 셀의 값이 같은지 확인하여, 합성할 수 있는지 여부를 판단
• 합성이 가능할 경우 두 셀을 합쳐 값이 2배가 된 새로운 셀을 만들고, 재귀적으로 연쇄 합성 가능성을 고려하여 경우의 수 누적
• 합성하지 않았다면 이전 상태의 경우의 수를 그대로 이어받음

 

3. dp[i]에 각 단계까지의 누적 경우의 수를 저장하고 마지막에는 해당 세그먼트에서 가능한 모든 합성 결정의 경우의 수가 저장됩니다.

 

4. 파라미터로 전달되는 a는 여러 세그먼트로 나뉘어 있으므로, 각 세그먼트마다 위 과정을 독립적으로 수행한 뒤 최종 결과 dp[segmentEnd]를 반환합니다.

 

 

개발환경: Programmers IDE   

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~