6362 - Unimodal Palindromic Decompositions

https://www.acmicpc.net/problem/6362

$N=7$일 때 아래와 같이 표현할 수 있다.

[그림 1]

가운데 숫자를 회색숫자(1,2,3..)만큼 쪼개서 양쪽에 붙인다고 생각했다. [그림 1]은 해석하면 [그림 2]와 같은 뜻이다.

[그림 2]

하지만 문제의 정의상 가운데에서 끝으로 갈수록 숫자가 (같거나) 작아야하므로 (3 1 3) 이나 (1 2 1 2 1) 같은 수열은 정답으로 셀 수 없다. 따라서 쪼개는 수(회색숫자)를 $k$라고 했을 때, $k \le n-2k$ 인 경우에만 쪼갤 수 있다. 

$k$는 쪼개서 옆에 붙인 숫자이다. 이 말은 가장 끝에 $k$ 보다 큰 수는 없다는 것이다. 항상 $k=1$ 가 아닌 $k=$이전의 $k_{prev}$ 부터 시작해야 한다.

짝수의 경우 역시 위와 동일하게 진행하되, (8) -> (4 4) 와 같은 경우가 가능하기 때문에 $k \le \frac{n}{2}$ 인지를 더해준다.

참고로 $N=8$ 일 때 (1 2 2 2 1) 에서 (1 2 1 1 2 1) 을 안 세도록 해야한다.

2705 - 팰린드롬 파티션

https://www.acmicpc.net/problem/2705

7을 팰린드롬 파티션으로 표현하면 아래와 같다.

       7
   1+  5  +1
   2+  3  +2
  1+1+ 3 +1+1
  3+   1   +3
1+1+1+ 1 +1+1+1

가운데를 축으로 보고, 양쪽으로 갈라지는 수에 대해 다시 재귀적으로 그것들을 축으로 센다.

아래와 같은 점화식으로 표현 가능하다.
$$ f(n) = 1 + f(0) + \dots + f(n/2) $$
1은 자기 자신을 나타내는 가짓 수이기 때문에 매번의 분열마다 더해준다.

1174 - 줄어드는 수

https://www.acmicpc.net/problem/1174

나올 수 있는 가장 큰 값은 9876543210 (10자리) 이다.
1자리 수(0~9)부터 10자리 수에 대해서 각각 감소하는 수를 모두 구하면 된다.
n자리로 이루어진 모든 감소하는 수는 재귀로 구현했다.

유사한 문제

- 1038번: 감소하는 수

2661 - 좋은수열

https://www.acmicpc.net/problem/2661

처음에는 Naive한 코드를 만들었다. N<20 정도에 대해서 출력을 살펴보기로 한 것이다. 출력이 아래와 같았다. (출력 자체만으로 힌트는 충분했다.)

1
12
121
1213
12131
121312
1213121
12131231
121312313
1213123132
12131231321
121312313212
1213123132123
12131231321231
121312313212312
1213123132123121
12131231321231213
121312313212312131
1213123132123121312

앞의 수열이 계속 유지되면서 위에 1/2/3 중에 하나가 계속 붙는다. (자세히보면 N=7 과 N=8 인 수열은 조금 다르다.)

이전의 수열($a_k$)에 1/2/3 중에 하나를 붙여서 "인접한 두 개의 부분 수열이 동일한 것이 있는 지"를 확인하고, 없다면 조금 더 이전($a_{k-2}$)부터 다시 만들어보면 된다.
이렇게 하면 k-2 부터 다시 재귀를 하는건데, (1/2/3을 선택)^3 = 9번만 해보면 되니까 얼마 안걸린다. (이전의 수열은 유지된다)

1062 - 가르침

https://www.acmicpc.net/problem/1062

k개의 알파벳을 학습하여 N개의 남극언어 중 몇 개를 읽을 수 있는가인데, 시간 복잡도 계산 안하고 그냥 재귀로 돌려봤다 (패기..!)

매번 모든 알파벳을 검사하기는 힘들다. 그리고 어차피 알파벳은 한번만 배우면 계속 쓰일 수 있다. 그럼 각 단어마다 알파벳의 존재여부를 체크하여 저장할 수가 있는데, 한 단어에서 x번째 알파벳이 사용되었다/안되었다(0/1) 로 구분하면 26자리 2진수 (최대 $2^{26}-1$) 로 표현할 수 있다. 그럼 ACE 는 0 00000 00000 00000 00000 10101 로 표현된다.
소스는 1번째...26번째로 해서 비트가 왼쪽으로 하나씩 밀려있다.

A~Z 중에 k개를 선택했을 때 읽을 수 있는 최대 단어의 갯수를 반환하면서, 그 최대값을 갱신하도록 했다.

그리고 "K개의 글자"에 남극언어에 들어가는 ANTA,TICA 도 포함되어야 한다. (이것때문에 한참 틀렸다) 즉, 5개의 글자(ANTIC)를 반드시 배워야한다는 것이다.

10971 - 외판원 순회 2

https://www.acmicpc.net/problem/10971

어떤 지점 s에서 출발해서 모든 정점을 거치고 다시 s로 돌아오는 경우를 모두 탐색했다. $O(N!)$
매 번 "모든 정점을 방문했는가?" 를 확인하면서 모두 방문했다면 현재가 s인가(출발점 == 종료점)를 판별해서 그렇다면 그때의 값이 최소가 되게 했다.

이동할 때마다 가중치를 더한다. 모든 정점을 방문했을 때 자신으로 돌아온게 아니라면 답이 아니도록 했다.

어떤 지점 s는 어디건 상관없다. 출발점과 도착점이 같은 지점을 찾는다면, 그 지점이 어디건 정답인 경우의 경로는 똑같이 나온다.

MFC 미로 게임

Maze Generator

매번 만들어야지 생각만 하다가, 드디어 해봤다.
오랜만에 MFC를 잡아서인지 몇 시간 걸렸다.
이전에 선배 도와주면서 만들어본 "DFS와 BFS를 이용한 최단경로" 를 적용해서 [Find Path] 버튼을 추가할 예정.

역시 알고리즘은 이렇게 써먹으면 기분 좋음

한가지 재미있는 사실이라면, srand(time(NULL)) 같이 time함수를 잘 쓰지 않는 편이라 (온라인 저지 탓인ㄱ..) rand함수를 잘 사용하지 않았다.
그럼 어떻게 하느냐
srand((int)&val)); 과 같이 특정 변수의 주소를 정수로 변환해버린다.
그런데 이게 지역변수라 매번 할당을 다르게 할 줄 알았더니, Generate 버튼을 아무리 눌러도 항상 같은 미로를 만들었다. 주소값이 같은건가..!!
덕분에 좋은 난수 생성 알고리즘을 알았는데, 메르센 트위스터(MT) 고안자가 만든 WELL512 를 사용해봤다. 자세한 내용은 구글링 + 위키 참조

---

10-06 15:48 update. v1.2

- 셀 크기 설정 추가 (가로X세로에 대해 자동 계산)

- 정답 출력(Find Path) 추가

- 미로만 다시 그리기(Reset) 추가

여담:
- 셀 크기가 너무 작거나 크면 미로를 만들지 않도록 했는 데 먹히질 않는다 (!!)
- 셀 크기가 너무 작으면 튕긴다. 주의..
- BFS 과정 출력 버튼도 있었는데 너무 더러워서 제거 (....)

---

10-06 18:55 update. v1.3

- 랜덤하지 못하게 편향된 경로 결과 수정
- 셀 크기를 변경하고 Find Path를 누르면 잘못되던 버그 수정

---

10-06 20:37 update. v1.4.0

- 버튼 활성화/비활성화 추가
- 최소 셀 크기 제한
- 버튼 UI를 왼쪽으로 이동
- 숫자 입력 후 엔터 누르면 자동 Generate 반복문이 맞물려서 런타임 에러가 남. 일단 삭제
- 창 크기 및 출력 크기 변경 가능

---

10-10 20:02 update. v1.4.1

- 인쇄 기능 추가 (세로 모드로 출력)
- 왼쪽 상단에 미로의 크기 정보 표시
- 미로 난이도 상향 (...?)
- 길 찾기 결과 출력에 옵션 추가. (탈출로 / BFS 결과)
- 시작점과 출발점을 변경함 (윗쪽 중앙에서 아랫쪽 중앙으로 탈출)
- 그 외 기타 예외 처리.

Attached File
> Maze_Generator.v1.4.1.exe

9461 - 파도반 수열

작년 ACM 본선 문제.

단순한 규칙성 문제라 정답은 아래 정의 하나로 끝나지만 몇가지만 조심하면 된다.

파도반 수열의 N번째 항은 P(N) = P(N-2) + P(N-3); 과 같이 나타낼 수 있다.

하지만 재귀식이므로 DP를 이용해서 꼭! 시간복잡도를 줄여야한다.

1012 - 유기농 배추

DFS나 BFS와 같은 전탐색으로 문제를 해결할 수 있다.
필자는 DFS를 사용했는데, int dirt[4]={-1,0,1,0}; 과 같이 선언하고

08	int DFS(int y, int x, int H /*최대 높이*/, int W /*최대 너비*/)

09

{

10	if( /* Base Case; 기저 케이스 */ ) return 0;

15	for(int i=0; i < 4; ++i)

16	DFS( y+dirt[(i+3)%4], x+dirt[i], H, W );

17

return 1;

18

}


위와 같이 [상(-1,0), 우(0,-1), 하(+1,0), 좌(0,+1) ]의 조합을 배열 하나로 사용했다.

여기서 DFS가 return 1; 을 했다. 이건 한 덩어리(구간)의 출발점만 리턴될 것이다.
왜냐하면 기저 케이스에서 "방문한 노드"는 return 0; 으로  걸러질 것이기 때문이다.

1759 - 암호 만들기

재귀적인 탐색 문제이다.

문제에서 "최소 1개의 모음과 최소 2개의 자음" 이라는 부분을 놓쳐서 몇 번 틀렸다.

재귀함수는 아래와 같다.

void password( int cur, int k, int N, int C /*Consonant*/, int V /*Vowel*/ ){
    if( k >= N && C > 1 && V > 0 ){
        // 누적된 문자열 출력
        return;
    }
    // ....
}

글자수가 제한되어 있으니 재귀 호출의 깊이를 제한하면 된다.
깊이의 제한을 위해 k로 깊이를 인자로 넘기고, N은 문제에서 말한 암호의 길이이다.

cur은 알파벳이고, 처음에 입력받은 알파벳들은 정렬 후 사용했다. (사전순 출력을 위해)