9518 - 로마 카톨릭 미사

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

다른 사람 소스를 보니까 내가 너무 어렵게 생각했던 것 같다.

(i, j)에서 주변 각 8방향에 대해 악수를 했다/안했다로 xxxxxxxx의 비트로 저장해서 주변 8방향을 하나씩 악수했다. (비트를 참고하여 이미 악수했다면 횟수로 세지 않았다.)

10472 - 십자뒤집기

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

3x3칸 크기의 보드를 1자로 펼치면 000 000 000 의 형태가 나온다. 각 칸의 상태를 */. 을 0/1로 표현하면 $2^9$ 가지 상태가 있다.

각 칸의 인접한 동서남북과 자신을 표현하면 아래와 같다.

int click[9]={
    416, //110 100 000
    464, //111 010 000
    200, //011 001 000
    308, //100 110 100
    186, //010 111 010
     89, //001 011 001
     38, //000 100 110
     23, //000 010 111
     11, //000 001 011
};

그리고 이 값을 XOR하면 그 칸을 선택하여 십자로 뒤집은 결과가 된다. 예를 들어, 101 000 010 의 가장 왼쪽 위칸을 십자로 뒤집으면 010 010 010 인데, 이건 101 000 010 XOR 111 010 000 이다.

너비 우선 탐색을 사용하여 000 000 000 부터 0~8번째 칸을 하나씩 뒤집어보면서 주어진 보드의 상태와 같아질 때 뒤집은 횟수를 출력하면 된다.

2098 - 외판원 순회

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

문제 <외판원 순회 2>의 실행시간이 오래 걸리는 이유는 모든 정점을 방문했는 지 확인하는 반복문과 이미 방문한 경로의 불필요한 탐색때문이다.

비트마스킹을 통해 이러한 반복을 줄여보자. 정점의 개수는 최대 16이다. 0번째, 1번째, ... 15번째를 방문했는지를 비트마스킹을 통해 00.....0 과 같이 길이가 16인 2진수로 표현할 수 있다. 그럼 $O(1)$만에 종료 조건을 확인할 수 있다.

하지만 모든 경우를 탐색하는 것은 똑같아서 수행시간에 큰 차이는 없을 것이다. (N배 빠르니까 약 10배)

여러 정점을 방문하면서 남은 정점을 확인할 때 중복되는 경우가 많다. 예를 들면 1 2 5 3 4 순으로 방문한 경우와 2 1 5 3 4 순으로 방문한 경우는 둘 다 1, 2를 방문한 상태에서 5 3 4 를 다시 방문하고 있다. 5 3 4 순으로 방문했을 때의 최적값을 구해둔다면 다시 방문할 필요 없이 미리 구한 최적해를 사용하면 된다. (메모이제이션으로 구현함)

이전에 작성한 글에서 소스의 다른 부분은 모든 정점을 방문했는 지 확인하는 반복문을 없애고 O(1)의 비트로 확인한다는 점과, 메모이제이션을 적용했다는 점 밖에 다르지 않다.

2718 - 타일 채우기

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

2x1 크기의 타일로 4xN 크기의 타일을 채우는 경우의 수를 구하는 문제이다.

문제를 작은 문제로 쪼개야하는 데 발상보다는 과정이 쉽게 떠오르지 않아서 해결하는 데 오랜 시간이 걸렸다.

2xN 타일 크기의 문제와 똑같이 왼쪽부터 1줄씩 채워나가면서 완성해나간다. 하지만 이 문제는 높이가 4N이기 때문에 1줄을 채울 때 여러 개의 경우가 나온다.

[그림 1] 한 줄의 상태를 비트로 표현할 때의 정수

이 외의 경우(1010 이나 0001 등의 형태)는 나올 수 없다. 왜냐하면 "이전의 줄의 모든 칸은 채워져있다."라는 가정에서 나타나는 상태이기 때문이다. 이 가정이 성립하지 않으면 타일은 채워질 수 없다. [그림 1]에서 점은 빈 칸이고, x는 이미 타일로 채워진 칸이다 (그것이 어떠한 형태이건 채워졌다라는 상태만 의미한다.)

물론 [그림 1] 에서 1111 은 빠져있다. 필자는 1111을 0000과 동일한 상태로 봤기 때문이다. N일때 한 줄의 모든 칸이 다 차있다(1111)면 이것은 (N-1)에 대한 문제가 된다. - 자세한 것은 2N 타일링 문제 풀이 참조 - 따라서 1111 일때는 다음의 다음 칸(N-2)의 상태가 0000인 것과 같다.

그럼 한 줄의 상태로 모든 상태를 어떻게 표현하는가?

앞으로 채워야할 오른쪽의 타일에 대해 (위처럼 0000과 같이 표현된) 현재 상태로부터 진행될 수 있는 경우는 아래 그림과 같다.

[그림 2] 어떠한 상태로부터 진행될 수 있는 타일의 새로운 상태

파란색 점선 박스를 다음으로 채울 오른쪽 줄이라고 하자. 그럼 0000 으로부터 나오는 경우는 1001, 1100, 1111, 0011, 0000 과 같다. 마찬가지로 나머지 경우도 동일하다.

그렇다면 문제는 아래와 같이 쪼개어 표현이 가능하다.

f(N칸을 채우는 경우, 현재 상태) = 현재 상태로부터 만들 수 있는 다음 상태(N-1)의 개수

N이 0이 되는 순간 모든 줄을 확인했다는 의미이고 이 때의 상태가 0000(혹은 1111)이면 모든 줄을 채웠다는 의미이므로 하나의 개수로 치고, 그 외에는 잘못된 경우이다.

0000 -> 1111 -> 0000 을 한번에 넘어가는 N-2 때문에 N < 0 인 경우가 나온다. 이 때는 상태에 상관없이 불가능한 경우이므로 0 이다.

더보기

• 1793번: 타일링 (2xN 크기)
• 2133번: 타일 채우기 (3xN 크기)

소스 코드

2320 - 끝말잇기

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

단어를 첫글자와 마지막글자로 압축하고 재귀로 다음 단어가 가능하다면 진행하도록 했다.

매번 0~N-1 번째 단어를 모두 확인해야한다. (선택한 단어에 따라 가능한 단어가 바뀌기 때문)

이렇게 하면 16^16 인 것같다. 너무 많다. (16! 일수도 있는데 이것도 큼) 단어를 선택함에 있어서 순서만 다르고 조합이 같은 중복 선택(호출)이 분명 존재한다.

AE EA UA AU 같은 경우는 AE-EA-AU-UA 도 되지만, AU-UA-AE-EA 도 된다. (둘은 같다)

IE EE EI EO 는 EI-IE-EE-EO 도 되지만 EE-EI-IE-EO 도 된다. EO 입장에선 앞에서 무슨 순서로 오는 건 상관없다. 어떤 것을 사용했는가만 알면 된다.

N=16 이니까 n번째 단어를 사용했다/안했다고 표현하면 2^16 으로 표현이 가능하다. 그럼 재귀식은 (현재 위치, 이전까지 사용한 단어의 상황) 으로 중복을 제거할 수있다.

1175 - 배달

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

2차원 평면에서 S부터 2개의 C블럭을 모두 도달하는 최단 거리 BFS인데 조건이 있다.

같은 방향으로 2번 이상 이동할 수가 없다.

원래 BFS를 할때 visit[N][M] 처럼 했다면, "어디쪽에서 왔는가"도 추가해야한다.

그리고 2개의 C블럭을 모두 도달해야 한다. 이것을 C0, C1 으로 부른다면 어떤 지점까지 움직였을 때, 문제를 얼만큼 해결했는 가를 4가지 상태로 나타낼 수 있다.

1. C0, C1 을 모두 못 찾았다.
2. C0 을 찾았다
3. C1 을 찾았다.
4. C0, C1 을 모두 찾았다.

(C0를 찾았다, C1를 찾았다) 로 표현한다면 00, 10, 01, 11 로 나타낼 수 있고, 이를 2진수로 본다면 10진수 0, 2, 1, 3 이다.

4번의 상태가 나올때까지, 같은 방향으로 진행하지 않으면서, 이전에 왔던 위치에 이전과 똑같은 움직임으로 다시 방문하지 않고 (visit[y][x][previousDirect]), 그 때의 '얼만큼 찾았는 가'의 상태마저 같지 않은 경우만 탐색하면 된다.

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)를 반드시 배워야한다는 것이다.