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번째 칸을 하나씩 뒤집어보면서 주어진 보드의 상태와 같아질 때 뒤집은 횟수를 출력하면 된다.

1138 - 한 줄로 서기

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

N명이 줄을 서는 모든 가짓 수 중에서 정답을 만족하는 경우를 출력했다.

N명이 줄을 서는 경우의 수 = O(N!)
매 번 조건에 만족하는 지 확인 = O(N)

next_permutation 을 썼다.

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 크기)

소스 코드

JOI 2015/2016 qualifying round

JOI 2016 예선

Online Judge: https://www.acmicpc.net/contest/view/152

크롬에서 한국어 번역 기능을 써서 문제를 읽었다. 문장이 이상하면 영어로 번역했다.

문제 #1. 科目選択

(물리, 화학, 생물, 지구과학) 중 상위 점수 3개 + (역사, 지리) 중 상위 점수 1개
두 묶음을 나눈 뒤 정렬하고 더함.

문제 #2. ゼッケンの交換

문제에서 설명한대로 구현하면 정답.
a[j] mod k > a[j+1] mod k 이면 자리를 바꾼다. k를 2부터 m까지 진행한 후 배열 a의 상태를 출력한다.

문제 #3. ロシアの旗

주어진 국기를 러시아 국기의 형태로 바꿔야하는 데, 최소 몇 개의 칸의 색깔을 바꿔야 하는 지 출력하는 문제이다.

위에서부터 (흰색, 파란색, 빨간색) 의 형태이여야한다. 나올 수 있는 모든 경우를 만들어보고 최소값을 갱신했다. $O(N^{3}M)$
N이 작아서 괜찮다.

나올 수 있는 모든 경우는 [0, i) 이 흰색 / [i, j) 이 파란색 / [j, n) 이 빨간색 구간인 것이다.
매 경우마다 N*M만큼 돌면서 색이 다른 칸의 수를 셈.

문제 #4. JOI国のお散歩事情

개미 문제처럼 사람들의 위치와 진행 방향이 주어지면 T 초 후 Q 사람들의 위치는 어디인가 묻는 문제이다. (사람들은 위치가 겹치면 그 자리에서 멈춘다.)

i번째 사람에게서 진행 방향에 따라 -T 혹은 +T 를 한 것이 그 사람의 T초 후의 위치일 것이다. i번째 사람의 나중 위치가 i-1번째 사람보다 앞서있다면 둘은 충돌한다는 것이다. 그럼 두 사람이 멈추는 위치는 (a[i]+a[i-1])/2. 그리고 이 위치로부터 더 이전 (i-1번째보다 더 이전) 에 있던 사람들도 이 위치에서 멈춰야하므로 모두 다시 갱신한다.

문제 #5. ゾンビ島

N개의 마을 중 K개 마을은 좀비에게 지배되었고 K개의 마을로부터 S개 이하의 도로만큼은 숙박 요금이 다르게 적용된다. - 정확히는 요금 Q를 적용, 그 외에는 요금 P를 적용 - (단, 좀비에게 지배된 K개의 마을은 지날 수 없다), 그리고 마을을 지날때마다 숙박 요금(P 또는 Q)를 낸다.
1번 마을로부터 N번 마을까지 가는 최소의 숙박 비용을 구하는 문제이다.

BFS로 K개 마을로부터 S개 이하의 도로(주변 거리라고 생각하면 됨)로 갈 수 있는 마을은 요금 Q를 적용한다.

노드마다 가중치를 두고 최단경로 알고리즘을 사용하면 된다.
노드에 가중치를 둘 줄 몰라서(!) 안전한 마을->위험한 마을 = Q, 위험한 마을>안전한 마을 = P 로 두고 다익스트라를 사용했다.
마지막 마을은 숙박비를 제외한다.

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번만 해보면 되니까 얼마 안걸린다. (이전의 수열은 유지된다)

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 으로 표현이 가능하다. 그럼 재귀식은 (현재 위치, 이전까지 사용한 단어의 상황) 으로 중복을 제거할 수있다.