[백준 / 17135] 캐슬 디펜스

투굠이 2019. 12. 20. 00:27

1. 문제 이해

N 행, M 열, D 최대 거리

N 행의 끝에 M개만큼 성이 있는데, 각 성에 최대 한 명씩 총 3명의 궁수가 있다.

그리고 배열로서 적이 주어진다 (1)

한 턴당, 적들은 행 +1 이 된다. ( 성으로 가까워진다)
성에 도달하게 되면, 적은 소멸 한다.

-조건 :
직각 거리로 D 보다 작으면서 가장 가까운 적을 골라 죽인다 ( 같은 거리가 있을 땐 열의 번호가 작은 거)

2. 문제 풀이법

먼저, 궁수 3명을 성에 위치시킬 방법은
조합으로 구하였다
!

그리고 조합이 만들어졌을 때, 게임을 실행시키는 방향으로 진행하였다.

게임이 실행될 때, 적들을 탐색하여 enemies라는 변수에 list 형태로 담았다!

그 enemies 가 다 없어질 때까지 반복문을 돌린다

enemies 반복문 내에선, 각 궁수마다 타기팅할 적의 번호(enemies의 index가 됨)를 저장한다.

그리고 그게 중복되었을 때 역시 없어지게 되므로 2번 해줄 필요가 없어 list -> set -> list 해서
sort 다시 해준 후 ( set으로 바꿀 때 갑자기 순서가 바뀌어서..) 끝에서부터 [::-1] 꺼내어 pop 해줬다.

pop 말고 다른 게 있나? 모르겠다. pop을 작은 순대로 했을 땐 그 뒤에 index 에러가 나서 이런 방법을 사용했다.

3. 어려웠던 점

1. 마지막 6번째 testcase가 안 맞아서 고생!
=> 행과 열 N M을 헷갈렸었다.

2. 중간에 temp에 이상한 변수를 넣어서 자꾸만 오류가 났었다.

1
 
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

import sys
sys.stdin = open('17135.tx')
 
N, M, D = map(int,input().split())
ground = [input().split() for _ in range(N)]
archers = [0,0,0]
castle = [_ for _ in range(M)]
enemies = []
ans = 0
 
def play(archer):#인자로 필요없나!?!?!?!?
    cnt = 0
    for i in range(N):
        for j in range(M):
            if ground[i][j] == '1':
                enemies.append([i,j])
    
    while enemies:
        target =[]
        for archer in archers: # [0,archer]로 사용해야함!
            temp = [-1,100000] # 적의 번호, 거리
            for i in range(len(enemies)): # 이샛기는 적 번호임ㅇ
                dist = (N - enemies[i][0]) + abs(archer-enemies[i][1])
                if dist > D or dist > temp[1]: # 클때
                    continue
                if  dist == temp[1] and enemies[i][1] > enemies[temp[0]][1]:
                     continue
                temp = [i,dist]
            if temp[0] != -1:
                target.append(temp[0])
 
        target = sorted(list(set(target))) # 중복제거하면 뭐이상하게되서 이렇게했슴
        
        for i in target[::-1]:
            enemies.pop(i)
            cnt += 1
        
        for i in range(len(enemies)-1,-1,-1):
            # print(i)
            enemies[i][0] += 1
            if enemies[i][0] == N:
                enemies.pop(i)
    return cnt
 
 
 
def comb(n,r):
    global ans
    if r == 0:
        temp_cnt = play(archers)
        if ans < temp_cnt:
            ans = temp_cnt
        
    elif n < r:
        return
    else:
        archers[r-1] = castle[n-1] # 헷갈림 주의!
        comb(n-1,r-1)
        comb(n-1,r)
 
comb(M,3)
 
print(ans)
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

4. 배운 점

4시간 이상의 시간을 들여서 풀었다.
더 깔끔히 풀고 싶은데! 나는 여하튼 이렇게 풀었다. 시간이 있으면 enemy를 만들지 않고 그냥 1을 옮겨가면서 해 보는 방법도 써 보고 싶다!

근데 최백준 님 알고리즘 강의 들었으면서 자바 볼 줄은 모르지만 뭔가를 많이 배운듯한? 느낌을 받는다

이래서 배움이 중요하구나 생각했다.

- list 중복 제거하는 법

a = [1,2,3,1]
a = list(set(a))
a => [1,2,3]

주의할 점 : 순서가 바뀔 수 있다

- index 거꾸로 가져오는 법

for i in range(len(enemies)-1,-1,-1):