DRAGON self review

[dakyommii]

DRAGON self review

• 파일명: DRAGON/dakyommii.cpp
• 수행시간: 4ms

1. 문제 해결 과정

시도1: 각 차원 최소 길이를 구하는 함수없이 차원 별로 문자를 치환하는 재귀함수만 구현했는데 치환했을 때 이전 차원보다 문자열 길이가 늘어나는 문제를 해결하지 못해서 실패했습니다. 그리고 함수를 통해서는 최종적인 문자열만 return 한 후 출력하려는 부분은 main 함수에서 잘라서 출력하려고 했습니다.

시도2. 각 차원에 대한 문자열 길이를 미리 지정하니까 치환했을 때 문자열의 길이를 조정해야하는 문제가 해결되었습니다. 또한 함수 내에서 최종 문자열을 모두 return하는 것이 아니라 출력할 문자를 return하는 것으로 수정하니 코드가 더 깔끔해졌습니다. 대신 현재 탐색하는 위치를 파악하기 위한 변수를 추가해서 목표한 문자를 출력할 수 있도록 처리했습니다.

2. 아이디어

동적계획법으로 풀었습니다.
X는 X+YF, Y는 FX-Y로 치환되는 것을 활용해 X와 Y의 개수를 함수로 표현해보면 length(N) = length(N-1) * 2 + 2로 표현할 수 있는 것 활용해 각 차원의 최소 길이를 구하는 함수 lenCnt()와
재귀로 문자 치환하고 최종적으로 목표하는 문자 차례대로 return 하는 함수 change()로 나눠서 풀었습니다.

3. 코드 설명

각 차원 최소 길이 저장하는 함수

void lenCnt() {
    len[0] = 1; //0차원에서는 FX라서 X 길이 1
    for (int i = 1; i < 51; i++)
        len[i] = min(MAX, len[i-1] * 2 + 2);    
}

X가 치환될 때
이전차원 X 길이 + 이전차원 Y 길이 + (F,+까지 해서 2개 추가)
이런 원리로 len[i-1] * 2 + 2로 표현합니다.

차원마다 문자열 치환하고 목표 문자 출력하기 위한 함수

char change(int N, int skp, const string& S) {    //skp: 출력 하려고 하는 문자열 판단 위한 변수
   if (N == 0) return S[skp];  //0차원이면 그냥 반환
   
   for (int i = 0; i < S.size(); i++) {
       if (S[i] == 'X' || S[i] == 'Y') {
           //skp를 차원의 최소문자 길이와 비교해서 skp가 더 작은 시점에는 차원을 모두 돌아서 최종적으로 출력해야할 시점
           
           if (skp >= len[N]) skp -= len[N];
           else if(S[i] == 'X')    //X자리 대체
               return change(N-1, skp, "X+YF");
           
           else if(S[i] == 'Y')    //Y자리 대체
               return change(N-1, skp, "FX-Y");
       }
       else if(skp > 0) --skp; //이 경우는 F,+,-인 경우이므로 다음 문자 검사하기 위해 skp 줄임
       else return S[i];   //최종 문자 return
   }

   return '#'; //오류
}

0차원이면 그대로 반환하도록 하고 나머지는 문자열의 모든 자리를 탐색하도록 했습니다.
i번째 문자가 X이거나 Y이면 치환한 후 다음 차원으로도 치환하고 return해주기 위해 재귀호출을 했습니다.
그리고 skp가 0보다 클 경우는 X,Y가 아닌 F,+,-인 경우이므로 다음 문자를 출력하기 위해 skp를 감소합니다.
마지막으로 skp가 0인 경우는 목표 문자에 도달한 경우이므로 i번째 문자열을 return합니다.