동적 계획법 테크닉 문제 2 드래곤 커브

이한울·2019년 7월 30일
0

DP 테크닉

목록 보기
3/6

문제 파악

처음 문제를 봤을 때는 세대 별 규칙을 파악해서 그 세대에 해당하는 문자열부터 시작해서 아래 세대로 쪼개서 내려가면서 해당 위치에 있는 문자열들을 찾는 방식일 것이라고 어렴풋이 생각했다.
세대 별 문자열들 간의 규칙 까지는 찾았는데 해당 문자열들을 찾아나가는 방식이 생각이 나지 않았다.
내가 생각했을 때 세대 별 문자열을 모두 만들어 놓고 해당 문자열을 찾는 식으로 접근하면 비효율이 발생할 것 같았다.

문제 풀이

풀이법은 세대 간의 규칙을 통해 찾는 방식이 아니라 주어진 문자열에 대해 처음 부터 확인하면서 나아가는 방식이다. 들어온 문자열에 대해 X, 또는 Y를 만나게 되면 재귀적으로 X또는 Y가 치환되는 문자열을 입력으로 세대 수를 낮춰 재귀적으로 호출한다. 이 때 k번째 문자를 찾는 방식은 기존 문제와 같이 전역 변수로 skip을 두어 skip이 0이 된 경우를 출력한다. 이렇게 k번째 문자를 찾는 과정을 l만큼 반복해 찾고자 하는 문자열을 만든다.

profile
Backend Engineer 이한울입니다

0개의 댓글