2023 04 21

backtracking(가능한 수열 중  최솟값 구하기)

• 수열에서 인접한 두 연속 부분 수열이 같은지 확인하기
  • 각 연속 부분 수열의 길이를 정하고 시작 및 끝 인덱스를 정한다.
    • 두 인접한 연속 부분 수열의 길이가 len = 1 이고, seq1의 시작 인덱스를 0(start1 = 0)이라고 한다면, seq1의 끝 인덱스는 start1 + len - 1이 될 것이다(end1 = start1 + len - 1).
    • start1이 0이고 end1이 0이니까, seq2의 시작 인덱스(start2)는 start2 = end1+1이 되고,  end2 = start2 + len - 1이 될 것이다.
    • 반복문을 통해 인접한 두 연속 부분 수열이 같은지 확인했다면, 길이(len)를 하나 늘리고 start1은 시작인덱스로 고정되어 있으니 end1, start2, end2를 계산해서 길이가 2인 인접한 두 연속 부분 수열이 같은지 반복문을 통해 확인할 수 있다.
    • 이런식으로 가능한 길이까지 다 확인했다면, start1(seq1의 시작인덱스)를 1늘려서 다시 인접한 두 연속 부분 수열의 길이가 같은지 확인한다.
  • 뒤에서부터 시작인덱스를 정하면 중복 검사를 피할 수 있다.