[백준] 17135 캐슬디펜스

1. 문제

www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

2. 접근방법

재밌는 시뮬레이션 문제

조합이 살짝 가미되어있다.

 

궁수 3명을 마지막행 아래에 배치시켰을때

거리에 맞춰 적을 죽이고 죽이고 난뒤엔 적이 한칸씩 내려온다.

이렇게 적이 다 내려왔을때 가장 많이 죽일 수 있는 위치를 찾아 그 때 죽인 적의 수를 구하는 문제

 

 

단 적을 죽일 때 자신의 위치에서 가장 가까운 거리의 적을 죽여야하고 거리가 같은 적이 여러명이라면 가장 왼쪽 적부터 죽인다.

또 3명의 궁수는 동시에 활을 쏘기 때문에 같은 적을 쏠 수도 있음에 주의하면서 풀어야한다.

3. 풀이

1. 궁수를 배치시킬 수 있는 모든 조합 구하기

2. 각 궁수가 자신의 위치에서 조건에 맞춰 죽일 적을 찾아 배열에 저장 해두기

3. 죽일 적을 모두 찾으면 적을 죽여 죽인 적의 숫자를 카운트하기 단 같은 적을 죽이면 카운트 하지 않기

4. 적이 한칸씩 내려가기 성까지 내려온 적은 사라진다.

5. 모든 적이 사라졌으면 카운트한 죽인 적의 수 저장

6. 모든 배치의 경우에 대해 가장 많이 죽인 적의 수 출력

 

4. 자바 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P17135캐슬디펜스 {
	static int N, M, D;
	static int[][] map, clone;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		clone = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		comb(0,0);
		System.out.println(result);

	}

	static int[] sel = new int[3];
	static int result = 0;
	static void comb(int idx, int selidx) {
		if (selidx == 3) {
			result = Math.max(result, simul());
			return;
		}
		if (idx >= M)
			return;

		sel[selidx] = idx;
		comb(idx + 1, selidx + 1);

		comb(idx + 1, selidx);
	}

	static void clonemap() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				clone[i][j] = map[i][j];
			}
		}
	}

	static int simul() {
		clonemap();
		int cnt = 0;
		while (true) {
			cnt += kill();
			if (down() == 0)
				break;
		}
		
		return cnt;
	}

	static int kill() {
		//그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다.
		//같은 적이 여러 궁수에게 공격당할 수 있다.
		int killman = 0;
		Point deathPoint [] = new Point[3];
		gg:for (int arr = 0 ; arr < 3 ; arr++) {
			int arrow = sel[arr];
			for (int d = 1; d <= D; d++) {
				for(int j = -d+1 ; j <= d-1 ; j++ ) { //i는 활쏠 row j는 활쏠 col
					int i = (d - Math.abs(j));
					if(i<0 || i >= N)
						continue;
					if(arrow +j >= 0 && arrow+j <M) {
						if(clone[N-i][arrow+j] == 1) {
							deathPoint[arr] = new Point(i,j);
							continue gg;
						}
							
					}
				}
			}
		}
		for(int idx = 0 ; idx< 3 ; idx++) {
			if(deathPoint[idx] == null)
				continue;
			int i = deathPoint[idx].x;
			int j = deathPoint[idx].y;
			int arrow = sel[idx];
			if(clone[N-i][arrow+j] == 0)
				continue;
			clone[N-i][arrow+j] = 0;
			killman++;
		}
		return killman;
	}

	static int down() {
		int remain = 0;
		for (int i = N - 1; i >= 0; i--) {
			for (int j = M - 1; j >= 0; j--) {
				if (clone[i][j] == 1) {
					clone[i][j] = 0;
					if (i + 1 >= N)
						continue;
					clone[i + 1][j] = 1;
					remain++;
				}
			}
		}
		return remain;
	}
}

5. 마치며

단 적을 죽일 때 자신의 위치에서 가장 가까운 거리의 적을 죽여야하고 거리가 같은 적이 여러명이라면 가장 왼쪽 적부터 죽인다.

또 3명의 궁수는 동시에 활을 쏘기 때문에 같은 적을 쏠 수도 있음에 주의하면서 풀어야한다.

 

이 조건에 안맞춰 풀다가 틀렸습니다 두번 받았다

제발 조건 좀 잘 읽자 ..ㅠㅜ