SLENDER ANKLES's 개발블로그

분할 정복 문제였다. 

문제를 간략히 정리하자면 

2의 7승까지의 크기를 갖는 정사각형 모양의 색종이를 

규칙에 맞게 잘랐을 때의 흰색부분, 핑크색 부분의 개수를 알아내는 문제였다. 

분할정복의 재귀함수의 인자를 가장 위, 가장 아래, 가장 왼쪽, 가장 오른쪽

이렇게 4가지의 인자를 가지고 있게 했다. 

2가지의 조건

1) 현재의 사각형이 같은 색깔이면 색종이 확정

2) 사각형이 더 이상 쪼갤 수 없이 1개이면 색종이 확정

을 만족하는 것 이외에는

// - 세로 시작 - 세로 중간 - 가로시작 - 가로중간

// - 세로시작 - 세로 중간 - 가로중간 - 가로끝 

// - 세로중간 - 세로끝 - 가로시작 - 가로중간

// - 세로 중간 - 세로끝 - 가로중간 - 가로끝

이렇게 색종이를 쪼갠다. 

중요한 것은 

[1] [2] [3] [4]

(1 + 4) / 2 => 2, (1 + 4) / 2 + 1 => 3

과 같이 왼쪽 오른쪽, 위 아래의 자르는 사각형의 범위를 신경써주면 된다. 

재귀를 통한 탐색방법에 대해서 다시 한 번 생각하고 명확히 알아야겠다는 필요성이 있었다. 

문제는

축사보안을 위한 L개 자리의 서로 다른 알파벳을 갖는 비밀번호를 생성하는 문제였다. 

입력으로 C개의 알파벳이 주어지는데, 

이 알파벳을 이용해서 L개 자리수를 가지는 알파벳을 만든다. 

조건이 있다면, 

1) 알파벳이 오름차순으로 정렬된 결과만을 도출해야 하며

2) 비밀번호에 모음이 1개 이상, 자음이 2개 이상 있어야 한다. 

완전탐색이긴 하지만 몇 가지 조건을 주어서 재귀적으로 풀어나가야 한다는 것을 알았다. 

입력의 상황

L => 4, C => 6

a t c i s w

가 주어지는데

우선 사전식 오름차순으로 먼저 정렬한다. 

a c i s t w

로 만들고

첫 번째 자리를 C - L => 2번째 인덱스까지 

배치하며 그 상황에 대해서만 완전탐색을 했다. 

4개의 알파벳 모음이 만들어 지면 모음이 한 개 이상 있는지만 검사해서 답을 내주었더니 답이 나왔다.

자음은 신경쓰지 않았다. 테스트케이스에 모음으로만 구성되어 있는 것이 없었나보다.

다시 풀어 볼 문제