boj17135 문제링크

접근방법

1. 문제 설명에서 궁수의 위치는 N+1에 위치하며 3명의 궁수를 배치한다라는 구문을보고 이부분은 조합으로 풀려고 생각했습니다. 최대 열이 15이므로 15C3 = 455로 크게 문제되지 않을 크기라고 생각했습니다.
2. 조건을 잘걸어 재귀함수를 구현해 함수가 실행될때마다 궁수는 적을 선정하고 공격한 다음 그 후 적의 전진을 진행 시켜 풀이하겠다고 생각했습니다.

적을 선정하고 타격하는 함수 hunt()
적을 전진하는 함수 down()
궁수를 배치하는 함수 combi()
거리를 계산하는 함수 distance()

4가지를 사용해야겠다고 생각하고 문제를 풀었습니다.

느낀점

테스트케이스 6번을 틀려서 고치면 4번이 틀리는 상황이 연출됐는데
거리가 같을때를 정확히 지정해주지 않아서 이런 상황이 펼쳐졌는데..
거리가 기본값보다 작으면 교체하고 같을때는 y좌표를 확인해주는 방법으로 쉽게 해결했습니다.
처음 시작하기전에 골격을 잡고 갔다면 하지 않았을 실수였다고 생각합니다.

if(target[k].dist>check) {
		target[k].dist = check;
		target[k].x = i;
		target[k].y = j;
								
}else if(target[k].dist==check) {
		if(target[k].y > j) {
			target[k].x = i;
			target[k].y = j;
		}
}

import java.io.*;
import java.util.*;
public class boj17135 {
	static int row,col,dist,map[][],count,res,rest;
	static boolean isSelected[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine()," ");
		row = Integer.parseInt(stz.nextToken());
		col = Integer.parseInt(stz.nextToken());
		dist = Integer.parseInt(stz.nextToken());
		map = new int[row+1][col];
		isSelected = new boolean[col];
		res =0;
		for(int i=0;i<row;i++) {
			stz = new StringTokenizer(br.readLine()," ");
			for(int j=0;j<col;j++) {
				map[i][j] = Integer.parseInt(stz.nextToken());
			}
		}
		combi(0,0);
		System.out.println(res);
	}
	static int temp[][],hunter[];
	private static void combi(int idx,int cnt) {
		if(cnt == 3) {
			temp =new int[row+1][col];
			hunter = new int[3];
			int index =0;
			for(int i=0;i<row+1;i++) System.arraycopy(map[i], 0, temp[i], 0, col);
			for(int i=0;i<col;i++) {
				if(isSelected[i]) {
					hunter[index++]=i;
				}
			}
			count= 0;
			hunt();
			res = Math.max(count, res);
			return;
		}
		if(idx>=col) return;
		isSelected[idx] =true;
		combi(idx+1, cnt+1);
		isSelected[idx] = false;
		combi(idx+1, cnt);
	}
	private static void hunt() {
		Data target[] = {new Data(100,100, Integer.MAX_VALUE)
				,new Data(100,100, Integer.MAX_VALUE)
				,new Data(100,100, Integer.MAX_VALUE)};
		int check=0;
		for(int i=0;i<row;i++) {
			for(int j=0;j<col;j++) {
				if(temp[i][j]==1) {
					for(int k=0;k<3;k++) {
						check=distance(hunter[k],i,j);
						if(check<=dist) {
							if(target[k].dist>check) {
								target[k].dist = check;
								target[k].x = i;
								target[k].y = j;
								
							}else if(target[k].dist==check) {
								if(target[k].y > j) {
									target[k].x = i;
									target[k].y = j;
								}
							}
						}
					}
				}
			}
		}
		for(int i=0;i<3;i++) {
			if(target[i].x == 100 || target[i].y==100) continue;
			if(temp[target[i].x][target[i].y] ==1) {
				temp[target[i].x][target[i].y] = 0 ;
				count++;
			}
		}
		if(down()) {
			hunt();
		}else return;
		
	}
	private static boolean down() {
		rest =0;
		for(int i=row-2;i>=0;i--) {
			for(int j=0;j<col;j++) {
				temp[i+1][j] = temp[i][j];
			}
		}
		for(int j=0;j<col;j++)temp[0][j] = 0;
		
		for(int i=1;i<row;i++) {
			for(int j=0;j<col;j++) {
				if(temp[i][j]==1) rest++;
			}
		}
		if(rest==0) return false;
		else return true;
	}
	private static int distance(int y1, int x2, int y2) {
		return Math.abs(row-x2)+Math.abs(y1-y2);
	}
	static class Data{
		int x;
		int y;
		int dist;
		public Data(int x, int y, int dist) {
			super();
			this.x = x;
			this.y = y;
			this.dist = dist;
		}
	}
}