[17281] ⚾ - Java[자바]

 

 

| 문제 링크

 

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

17281번: ⚾

 

 

 

 

---

 

 

 

 

| 문제

 

1. 이닝의 수를 나타내는 N(2 ≤ N ≤ 50)이 주어지며, N 줄에는 이닝 별 선수들이 결과가 입력됩니다.
   0: 아웃
   i: 안타(i루), i (2 ≤ i ≤ 50)
   4: 홈런
   
2. 타자들의 순서를 정해 모든 이닝에 걸쳐 받을 수 있는 가장 높은 점수가 몇인지 출력하시오.( 1번 선수는 4번 타자로 고정)
   이닝은 3회 아웃되면 끝나며, 이닝이 끝나도 타자의 순서는 계속 이어집니다.
   

 

 

 

---

 

 

 

 

| 풀이

 

1. dfs를 통해 타자들의 순서의 모든 순열을 구합니다.
2. 순열별로 몇 점을 얻을 수 있는지 시뮬레이션을 동작시켜 max값을 출력합니다.

 

풀이 자체는 간단하나 타자의 순서를 순열로 나타내는 방법과 이닝별로 타자의 순서가 끊기지 않고 이어지는 부분을 생각하는 부분이 헷갈려 헤맸던 문제 입니다. 자세한 내용은 주석을 보시면 이해가 빠르실 거 같습니다.

 

 

 

 

 

---

 

 

 

 

| 코드

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	
	public static int ans;
	public static int inning;
	public static int[] dp = new int[3];
	public static int[][] expectedResult;
	public static int[] hitter = new int[9];
	public static boolean[] flag = new boolean[9];
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		//이닝별 예상되는 타자별 결과를 2차워 배열 expectedResult에 입력
		inning = Integer.parseInt(br.readLine());
		expectedResult = new int[inning][9];
		for(int r = 0; r<inning; r++) {
			st = new StringTokenizer(br.readLine());
			for(int c = 0; c<9; c++) {
				expectedResult[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		
		//hitter의 인덱스+1: 타자 번호
		//hitter의 값: 선수 번호
		//1선수는 4번타자로 고정
		hitter[3] = 1;
		flag[3] = true;
		//0(0+1)번 선수는 4번 타자로 고정이므로 depth 1부터 시작
		dfs(2);
		
		bw.write(String.valueOf(ans));
		br.close();
		bw.close();
	}
	
	public static void dfs(int depth) {
		if(depth==10) {
			//타자의 순서가 다 정해졌다면, 해당 순열로 얻을 수 있는 점수가 몇 점인지 구한다.
			int score = game();
			ans = Math.max(ans, score);
			return;
		}
		//i번째 타자에 몇 번 선수를 넣을지 순열을 생성
		for(int i = 0; i<9; i++) {
			//i번쨰 타자를 이미 구했다면 continue
			if(flag[i])
				continue;
			flag[i] = true;
			hitter[i] = depth;
			dfs(depth+1);
			flag[i] = false;
		}
	}
	
	public static int game() {
		int idx = 0;
		int sum = 0;
		int out;
		int hit;
		for(int i = 0; i<inning; i++) {
			//inning별 dp와 out 0으로 재할당, 초기화를 하면 메모리를 많이 차지함
			for(int c = 0; c<3; c++) {
				dp[c]=0;
			}
			out = 0;
			//이닝별 out이 3회되면 멈춤
			while(out<3) {
				//idx++%9 로  idx가 0부터 8을 반복하도록 구현
				hit = expectedResult[i][hitter[idx++%9]-1];
				if(hit==4) {
					sum+=dp[2]+dp[1]+dp[0]+1;
					dp[2]=0;
					dp[1]=0;
					dp[0]=0;
				}
				if(hit==3) {
					sum+=dp[2]+dp[1]+dp[0];
					dp[2]=1;
					dp[1]=0;
					dp[0]=0;
				}
				if(hit==2) {
					sum+=dp[2]+dp[1];
					dp[2]=dp[0];
					dp[1]=1;
					dp[0]=0;
				}
				if(hit==1) {
					sum+=dp[2];
					dp[2]=dp[1];
					dp[1]=dp[0];
					dp[0]=1;
				}
				if(hit==0)
					out++;
			}
			
		}
		return sum;
	}

}