규영이와 인영이의 카드게임
1. 문제 접근 방법 및 아이디어
이 문제는 규영이의 카드 순서는 고정되어 있고, 인영이가 가진 9장의 카드를 어떤 순서로 내느냐에 따라 승패가 결정되는 문제입니다.
- 데이터 분리
- 전체 1 ~ 18 카드 중 규영이가 가진 9장을 제외한 나머지 9장을 인영이의 카드로 분류합니다.
- 순서 결정
- 인영이가 카드를 내는 모든 가능한 순서(경우의 수)를 생성합니다.
- 점수 계산
- 각 순서마다 비교하여 승점을 계산하고, 최종 승리/패배 횟수를 카운트합니다.
2. 필요 개념 및 알고리즘
- 순열
- 인영이가 카드를 내는 순서가 중요하기 때문입니다.
- {1,2,3} 순서로 내는 것과 {3,2,1} 순서로 내는 것은 규영이의 카드와 대조했을 때 결과가 완전히 달라집니다.
- 백트래킹
- 모든 경우를 따져보고, 이미 사용한 카드는 다시 쓸 수 없으므로 방문 배열을 활욯한 상태 관리가 필수적입니다.
3. 어려웠던 점
- 인영이 카드 추출
- 규영이 카드를 제외한 나머지 카드를 추출하는 아이디어가 떠오르지 않았습니다.
4. 코드 풀이
4.1 데이터 분리
4.1.1 규영이 카드 체크
// 모든 카드 숫자
checkNum = new boolean[19];
// 규영이의 카드 입력
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < 9; i++) {
kyuArr[i] = Integer.parseInt(st.nextToken());
// 규영이의 카드 체크
checkNum[kyuArr[i]] = true;
}
- 1 ~ 18 카드 번호 확인하기 위해서 boolean 배열의 크기를 19로 합니다.
- 규영이의 카드가 입력되면 해당 카드 번호를 체크 배열 인덱스로 매칭합니다.
4.1.2 인영이의 카드 추출
// 인영이의 카드 세팅
int idx = 0;
for (int i = 1; i <= 18; i++) {
if (!checkNum[i]) {
inArr[idx++] = i;
}
}
- 1 ~ 18까지 반복하면서 규영이가 선택한 카드가 아닌 카드만 인영이 카드로 추출합니다.
4.2 경우의 수 게산
// 경우의 수 탐색
for (int i = 0; i < 9; i++) {
// 이미 방문한 곳이면 다음으로 넘어간다.
if (visited[i])
continue;
int sum = kyuArr[level] + inArr[i];
visited[i] = true;
if (kyuArr[level] > inArr[i]) {
dfs(level + 1, kyuSum + sum, inSum);
} else {
dfs(level + 1, kyuSum, inSum + sum);
}
visited[i] = false;
}
- 규영이와 인영이가 낸 카드를 비교해서 큰 쪽으로 두 카드의 합을 더합니다.
4.3 점수 계산
// 종료 조건
if (level == 9) {
if (kyuSum > inSum)
kyuWin++;
else
inWin++;
return;
}
- 규영이와 인영이의 카드 비교가 완료하면 그 합을 비교해서 누가 승리했는지 카운트합니다.
4.4 DFS 함수 코드
// 규영이와 인영이의 카드를 비교하는 함수
static void dfs(int level, int kyuSum, int inSum) {
// 종료 조건
if (level == 9) {
if (kyuSum > inSum)
kyuWin++;
else
inWin++;
return;
}
// 경우의 수 탐색
for (int i = 0; i < 9; i++) {
// 이미 방문한 곳이면 다음으로 넘어간다.
if (visited[i])
continue;
int sum = kyuArr[level] + inArr[i];
visited[i] = true;
if (kyuArr[level] > inArr[i]) {
dfs(level + 1, kyuSum + sum, inSum);
} else {
dfs(level + 1, kyuSum, inSum + sum);
}
visited[i] = false;
}
}
4.6 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
static boolean visited[]; // 방문 체크 배열
static int[] kyuArr, inArr; // 규영이, 인영이의 배열
static boolean checkNum[]; // 규영이가 선택한 숫자 확인
static int kyuWin, inWin; // 규영이, 인영이의 승리 횟수
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine().trim());
// tc 수행
for (int tc = 1; tc <= T; tc++) {
// 규영이, 인영이 배열 초기화
kyuArr = new int[9];
inArr = new int[9];
// 방문 배열 초기화
visited = new boolean[9];
// 규영이, 인영이 승리 횟수 초기화
kyuWin = 0;
inWin = 0;
// 모든 카드 숫자
checkNum = new boolean[19];
// 규영이의 카드 입력
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < 9; i++) {
kyuArr[i] = Integer.parseInt(st.nextToken());
// 규영이의 카드 체크
checkNum[kyuArr[i]] = true;
}
// 인영이의 카드 세팅
int idx = 0;
for (int i = 1; i <= 18; i++) {
if (!checkNum[i]) {
inArr[idx++] = i;
}
}
// 처리
dfs(0, 0, 0);
// 출력 내용 추가
sb.append("#" + tc + " " + kyuWin + " " + inWin + "\n");
} // tc 종료
// 출력
System.out.println(sb);
} // 메인 종료
// 규영이와 인영이의 카드를 비교하는 함수
static void dfs(int level, int kyuSum, int inSum) {
// 종료 조건
if (level == 9) {
if (kyuSum > inSum)
kyuWin++;
else
inWin++;
return;
}
// 경우의 수 탐색
for (int i = 0; i < 9; i++) {
// 이미 방문한 곳이면 다음으로 넘어간다.
if (visited[i])
continue;
int sum = kyuArr[level] + inArr[i];
visited[i] = true;
if (kyuArr[level] > inArr[i]) {
dfs(level + 1, kyuSum + sum, inSum);
} else {
dfs(level + 1, kyuSum, inSum + sum);
}
visited[i] = false;
}
}
}