순열, 비트마스킹
처음에 문제 제목에 이모지 하나밖에 없길래 번외 문제인 줄 알았습니다.
문제 📝 (Gold 4)
문제 링크는 다음과 같습니다.
https://www.acmicpc.net/problem/17281
접근 방법
주의 사항
문제를 잘 읽어야 됩니다. 이걸로 맞는데 왜 틀리지를 생각했던 것 같습니다.
아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다. 이제 다른 선수의 타순을 모두 결정해야 한다.
즉, 1번 선수가 4번 타자인 것은 고정으로 생각하고 진행해야 됩니다. 따라서 타순의 경우의 수는 (9 - 1)! 입니다.
그리고 혹시라도 수행횟수 체크를 해줍니다. 50 * 8! = 2016000 으로 이정도면 충분히 완전 탐색으로 가능합니다.
일반적인 접근 방법
그렇다면 진행해야 되는 구현 사항은 크게 두가지 입니다.
- 선수들의 순서를 정해주기
- 순서가 정해지면 실제 게임을 진행하기
1번은 순열 템플릿을 적용하되, 4번 타자는 고정이므로 cnt가 4 일 때는 다음으로 넘어가줍니다. 참고로 순열 템플릿을 아래와 같습니다.
import java.io.*;
import java.util.*;
public class PermMain {
static int N = 4, R = 3, C = 0;
static int[] a = {1, 2, 3, 4}, b = new int[R];
static boolean[] v = new boolean[N];
public static void perm(int cnt) {
if(cnt == R) {
System.out.println(Arrays.toString(b)); return;
}
for(int i = 0; i < N; i++) {
if(v[i]) continue;
v[i] = true;
b[cnt] = a[i];
perm(cnt + 1);
v[i] = false;
}
}
public static void main(String[] args) throws Exception {
C = 0;
perm(0);
System.out.println(C);
}
}위 순열 템플릿을 활용해서 다음과 같이 perm 메소드를 작성해줍니다.
static void perm(int cnt) {
if(cnt == 4) {
perm(cnt + 1); return;
}
if(cnt > 9) {
play(); return;
}
for(int i = 1; i < 10; i++) {
if(visited[i]) continue;
visited[i] = true;
order[cnt] = i;
perm(cnt + 1);
visited[i] = false;
}
}그런데... 낯썬 메소드 하나가 보입니다. 바로 play 메소드입니다. 이것이 바로 2. 순서가 정해지면 실제 게임을 진행하기 에 해당하는 메소드입니다.
구현 아이디어는 다음과 같습니다.
- 우선 이닝이 시작하면 홈에 타자가 들어온다.
- n루타의 경우에는 홈으로 들어올 타자들의 수를 계산(점수 증가)한다.
- 각각 n칸씩 이동한다.
- 아웃의 경우에는 아웃카운트만 증가시킨다.
- 아웃카운트가 3이면 이닝 종료. 베이스를 비워두고 다음타자부터 이닝 시작
차례대로 생각해봅니다.
우선 이닝 수 N에 대해서 for문을 돌리고, 베이스는 총 4개이므로 크기가 4인 boolean 배열(base)을 생각할 수 있습니다. true면 주자가 있는 것으로 생각하면 됩니다.
홈은 0, i(= 1, 2, 3)루는 i의 인덱스라고 생각할 수 있고, 홈에 타자가 들어오는 것은 base[0] = true로 둘 수 있습니다.
다음은 점수 계산을 해줍니다. 이동 전 점수 계산을 먼저해줄껀데, 물론 주자 이동하면서 계산해도 무방합니다. 이동 전 점수는 4 - n루의 상황까지 계산이 가능합니다. 이를 for문을 통해 score에 반영해줍니다.
다음은 n칸 이동입니다. 여기서 주의할 점이 몇가지 있습니다. 주자 1, 3루라 가정하겠습니다. 초기 상황은 다음과 같습니다.
| 홈 | 1루 | 2루 | 3루 |
|---|---|---|---|
| T | T | F | T |
여기서 안타를 치면 다음과 같습니다. 점수는 계산했다고 가정합니다.
| 홈 | 1루 | 2루 | 3루 |
|---|---|---|---|
| F | T | T | F |
즉 모두 한칸씩 이동인데, 여기서 주의할 점이 하나가 있습니다. 다음과 같은 pseudocode를 생각해보겠습니다.
For i = 1 To 3
base[i] = base[i - 1] // 앞쪽에서 하나씩 덮어쓰기
EndFor이렇게 수행시에 다음과 같은 결과를 얻게 됩니다.
| 홈 | 1루 | 2루 | 3루 |
|---|---|---|---|
| T | T | T | T |
??? 뭔가 이상합니다. 그 이유는 바로 덮어쓰면서 다음에 반영되어야 될 값이 오염되었기 때문입니다. 예시에선 1루에서 2루로 넘어갈 때 2루에 T가 반영되면서 3루에는 2루에 반영되어야 될 F가 사라지고 덮어씌워진 T가 반영됩니다.
그러면 다른 방법을 생각해야 되는데... 바로 뒤에서 부터 시작하면 오염이 되지 않습니다.
For i = 3 To 1
base[i] = base[i - 1] // 뒤쪽에서 하나씩 덮어쓰기
EndFor그러면 실행 결과는 다음과 같습니다.
| 홈 | 1루 | 2루 | 3루 |
|---|---|---|---|
| T | T | T | F |
??? 그래도 이상합니다. 홈에는 주자가 없어야 됩니다. 여기서 또다른 주의사항이 나옵니다. 바로 n루타로 주자가 다 이동하면 n루 뒤쪽은 깔끔하게 지워줘야합니다. 그러면 다음과 같습니다.
| 홈 | 1루 | 2루 | 3루 |
|---|---|---|---|
| F | T | T | F |
정리하면
- 점수 계산
- 주자 이동
- n루타 후 n루 뒤쪽은 깔끔하게 지워주기
이고, 이부분만 코드를 보면 다음과 같습니다.
// hit루타를 쳤다고 가정
for(int j = 3; j > 3 - hit; j--) if(base[j]) score++; // 점수 계산
for(int j = 3; j >= hit; j--) base[j] = base[j - hit]; // 주자 이동
for(int j = 0; j < hit; j++) base[j] = false; // 지우기남은건 아웃처리인데 간단합니다. 아웃카운트만 증가하고 continue입니다.
if(hit == 0) {
out++; continue;
}그리고 남은 조건들(이닝 종료, 다음 타자 준비 등)을 고려한 play 메소드는 다음과 같습니다.
static void play() {
int start = 1, score = 0; // 경기 자체의 시작은 1번 타자, 0점으로 시작
for(int i = 0; i < N; i++) {
int out = 0;
Arrays.fill(base, false); // 베이스 비워두기
while(out < 3) {
if(start > 9) start = 1; // 9번을 넘어가면 다시 1번으로
base[0] = true;
int hit = result[i][order[start++]];
if(hit == 0) {
out++; continue;
}
for(int j = 3; j > 3 - hit; j--) if(base[j]) score++;
for(int j = 3; j >= hit; j--) base[j] = base[j - hit];
for(int j = 0; j < hit; j++) base[j] = false;
}
}
answer = Math.max(answer, score); // 최댓값 갱신
}전체 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, answer;
static int[] order;
static int[][] result;
static boolean[] visited, base;
static void perm(int cnt) {
if(cnt == 4) {
perm(cnt + 1); return;
}
if(cnt > 9) {
play(); return;
}
for(int i = 1; i < 10; i++) {
if(visited[i]) continue;
visited[i] = true;
order[cnt] = i;
perm(cnt + 1);
visited[i] = false;
}
}
static void play() {
int start = 1, score = 0;
for(int i = 0; i < N; i++) {
int out = 0;
Arrays.fill(base, false);
while(out < 3) {
if(start > 9) start = 1;
base[0] = true;
int hit = result[i][order[start++]];
if(hit == 0) {
out++; continue;
}
for(int j = 3; j > 3 - hit; j--) if(base[j]) score++;
for(int j = 3; j >= hit; j--) base[j] = base[j - hit];
for(int j = 0; j < hit; j++) base[j] = false;
}
}
answer = Math.max(answer, score);
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
result = new int[N][10];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1; j < 10; j++) {
result[i][j] = Integer.parseInt(st.nextToken());
}
}
answer = 0;
order = new int[10];
visited = new boolean[10];
base = new boolean[4];
order[4] = 1;
visited[1] = true;
perm(1);
System.out.println(answer);
br.close();
}
}비트마스킹
그런데... 요즘 들어 습관이 하나 생겼습니다.
번호가 1 ~ 9, 베이스도 0, 1, 2, 3 밖에 안되는데 그냥 비트로 찍을까?
예... 비트마스킹입니다. 비트마스킹을 하면 몇 가지 이점이 있습니다.
- boolean 배열 대신 bit 단위로 찍음으로써 메모리 절약
- 구현의 편리함
비트필드(이 문제는 해당 X)
특히 주자 이동을 구현하는게 비트마스킹이 편리한 점이 있습니다. 비슷한 예로는 이런 문제 등이 있습니다.
점수 계산은 사실 기존과 별반 차이가 없습니다만, 주자 이동이 어떻게 편리해질까요? 다음과 같이 적으면 끝납니다.
base <<= hit;끝입니다. 바로 shift 연산을 통해 hit 아래 항목들을 0으로 채우기 때문에 가능합니다. 덤으로 for문도 덜 돌아서 속도도 좀 더 빨라집니다.
위가 비트마스킹, 아래가 일반적인 배열을 통한 방법입니다.
전체 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, answer;
static int[] order;
static int[][] result;
static void perm(int cnt, int visited) {
if(cnt == 4) {
perm(cnt + 1, visited); return;
}
if(cnt > 9) {
play(); return;
}
for(int i = 1; i < 10; i++) {
if((visited & (1 << i)) != 0) continue;
order[cnt] = i;
perm(cnt + 1, visited | (1 << i));
}
}
static void play() {
int start = 1, score = 0;
for(int i = 0; i < N; i++) {
int out = 0;
int base = 0;
while(out < 3) {
if(start > 9) start = 1;
base |= 1;
int hit = result[i][order[start++]];
if(hit == 0) {
out++; continue;
}
for(int j = 3; j > 3 - hit; j--) if((base & (1 << j)) != 0) score++;
base <<= hit;
}
}
answer = Math.max(answer, score);
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
result = new int[N][10];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1; j < 10; j++) {
result[i][j] = Integer.parseInt(st.nextToken());
}
}
answer = 0;
order = new int[10];
order[4] = 1;
perm(1, 1 << 1);
System.out.println(answer);
br.close();
}
}
