2014 한국 정보 올림피아드 지역본선 문제 풀이

1번은 그냥 규칙에 맞게 달팽이(나선) 테이블을 만들어주면 된다.

2번은 오른쪽이나 위쪽 벽에 부딪힌 후에의 움직임을, 그 부분에 표를 하나를 대칭시켜서 보면 된다.

무슨 말이냐면...

이것을

이렇게 생각하자는 것이지.(사실 여기서 위로 한번 더 뒤집어야 한다)

3번은 각각의 물건에서 다른 물건으로의 '방향간선'을 그어보면 전체가 DAG(Directed Acyclic Graph, 방향 간선으로만 이루어져 있고 사이클이 없는 그래프)임을 알 수 있다.

여기서 두 물건의 크기 비교가 가능하다는 것은 한 물건에서 다른 물건으로 가는 경로가 있는지를 판단하면 된다.

n<=100이기 때문에 (각 점에서 BFS)와 (플로이드) 혹은 (위상정렬 어쩌구..) 등 어느 알고리즘을 써도 쉽게 풀린다.

대망의 4번이다.

사실 여기부터가 본론이다.

N과 K가 주어진다.

(N≤100만, 3≤K≤26)

알파벳 'A'부터 ('A'+K-1까지의) K개의 알파벳을 써서,

길이가 N인 문자열을 만드는데,

그 문자열중에 'ABCBC'와 'ABABC'가 없는 문자열의 갯수를 세는 문제였다.

(여기서 ABABC 같은건 다 정확히 일치해야 한다!

처음에 패턴(예를들면 12123이나 xyxyz도 저런 것이겠다)으로 생각을 했는데 아니었다..)

갯수 세는 문제는 사실 대부분 결국 동적계획법 문제이다.

(재귀호출 같은걸로 일일이 갯수를 세는 문제도 있겠지만,

이 문제는 총 가짓수를 1000000009로 나누라고 한 것부터가 갯수가 굉장히 커질 것같다)

그러면 동적으로 계획을 하려면 이전 경우를 가지고(N-1 길이의 문자열을 만드는 경우의 수),

현재 경우를(N 길이의 문자열을 만드는 경우의 수) 구해야 한다.

그런데 조건때문에 그냥 f(N-1), f(N)으로 구하기가 힘들다.

자, 그럼 여기서 어떻게 할까?

일단은 모든 문자열을 분류했다.

A로 끝나는 문자열(ABA로 끝나는 것 제외)

AB로 끝나는 문자열(ABAB로 끝나는 것 제외)

ABC로 끝나는 문자열

ABA로 끝나는 문자열

ABAB로 끝나는 문자열

ABCB로 끝나는 문자열

다른 것들로 끝나는 문자열

그 후 각각을 동적 계획을 해보자.

A로 끝나는 문자열은, (N-1) 길이의 모든 문자열에다가 A를 붙이기만 하면 된다.

그런데! AB 혹은 ABAB로 끝나는 문자열에 A를 붙이면 ABA로 끝나는 문자열이 되므로 이 경우를 빼준다.

AB로 끝나는 문자열은 (N-1)길이의 A로 끝나는 문자열의 갯수와 같다.

ABA로 끝나는 문자열은 (N-1)길이의,

(AB로 끝나는 문자열의 갯수 + ABAB로 끝나는 문자열의 갯수)와 같다.

ABC로 끝나는 문자열은 (N-1)길이의 AB로 끝나는 문자열의 갯수와 같다.

(이때 AB가 ABAB를 포함하지 않기 때문에 그냥 C를 붙일 수 있다)

ABAB로 끝나는 문자열은 (N-1)길이의 ABA로 끝나는 문자열의 갯수와 같다.

ABCB로 끝나는 문자열은 (N-1)길이의 ABC로 끝나는 문자열의 갯수와 같다.

모든 문자열의 수는, ((N-1)길이의 모든 문자열의 수) * K - ((N-1)길이의 ABAB의 수) - (N-1길이의 ABCB 수)와 같다. (뒤에 한 문자를 붙이면 되니까)

그러면 동적계획법 배열을 만들어서,

[0] -> A로 끝남

[1] -> AB로 끝남

...

[5] -> ABCB로 끝남

[6] -> 모든 가짓수(위에 있는 것 포함)

[6]을 왜 저렇게 잡냐면,

어차피 다른 것들로 끝나는 문자열의 갯수는 사용할 일이 없다.

오히려 모든 가짓수를 구해놓으면 그다음 A의 갯수를 구할 때 편하기 때문이다.

또한 코딩할때,

#define 0 strA___

#define 1 strAB__

...

#define 5 strABCB

#define 6 strALL_

이런식으로 선언한 뒤에 점화식을 세우면 코드가 직관적이고 보기 좋다.

그런데! N이 100만까지 가고, 1000000009 나머지 연산을 쉽게 하기 위해,

long long을 쓰는게 편한데,

8바이트 100만 × 7 배열을 만들기가 좀.. 찝찝하다.

(연속하게 비어있는 5600만 바이트의 공간을 메모리 상에서 찾는데에 얼마가 걸릴지...)

그런데! 방금의 예에서 N-1 길이의 문자열만 필요했다.

오랜만에 블로그에 들어와서 두니발 박사에 관한 문제를 설명한 이유가 이것이다.

dyn[0]으로 dyn[1]을 구하고, dyn[1]으로 dyn[0]을 구하고, ...

이런 식으로 풀면 2×7 배열만 잡으면 된다. 

코드는 이런 식이었던거 같다.

#define strA    0
#define strAB   1
#define strABA  2
#define strABAB 3
#define strABC  4
#define strABCB 5
#define strSUM  6

typedef long long ll;

void work(ll from[], ll to[]){
	to[strA   ]=getMod(from[strSUM] - from[strABAB] - from[strAB]);
	to[strAB  ]=getMod(from[strA   ]);
	to[strABA ]=getMod(from[strAB  ]+from[strABAB]);
	to[strABAB]=getMod(from[strABA ]);
	to[strABC ]=getMod(from[strAB  ]);
	to[strABCB]=getMod(from[strABC ]);
	to[strSUM ]=getMod(from[strSUM]*k - from[strABAB]-from[strABCB]);
}

ll data[2][20];

main(){
	//

	int parity=0,i;
	data[0][strA   ]=1;
	data[0][strSUM ]=k;
	for(i=2;i<=n;i++){
		work(data[parity],data[1-parity]);
		parity^=1; // same as (data=1-data;)
	}

	//
}