글 읽기 - 제가 문제를 잘못 이해했나요? 반례좀 알려주세요

dolgodolah 3년 전 0

질문글에 있는 반례 찾아가면서 계속 수정하다가

50%대에서 틀렸습니다. 이 지점 반례는 검색도 안되고

혼자 소스보면서 반례 뭐있을지 생각해보고 있는데 도움 좀 주세요.

import copy
from itertools import combinations
n,m,d=map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))
graph.append([0]*m)#궁수가 위치할 성 위치 추가

def get_score(graph):
    temp_graph = copy.deepcopy(graph)
    died = [[False]*m for _ in range(n)]
    score = 0
    while True:

        # 공격
        for i in range(m):
            if temp_graph[n][i]==1:#궁수 위치 찾으면
                shoot = 0 #궁수 사격 여부
                for j in range(1,d+1):#거리순으로
                    #왼쪽부터(j==1일때는 수행x)
                    for k in range((j*2-1)//2):
                        if -1<i-j+1+k<m and -1<n-1-k<n and temp_graph[n-1-k][i-j+1+k]==1:
                            if died[n-1-k][i-j+1+k]==False:
                                died[n-1-k][i-j+1+k]=True
                            shoot = 1
                            break
                    if shoot>0:
                        break
                    
                    #가운데
                    if -1<n-j<n and temp_graph[n-j][i]==1:
                        if died[n-j][i]==False:
                            died[n-j][i]=True
                        break
                    
                    #오른쪽
                    for k in range((j*2-1)//2):
                        if -1<n-1-k<n and -1<i+j-1-k<m and temp_graph[n-1-k][i+j-1-k]==1:
                            if died[n-1-k][i+j-1-k]==False:
                                died[n-1-k][i+j-1-k]=True
                            shoot=1
                            break
                    if shoot>0:
                        break
      
        #궁수 사격 턴 끝나고    
        #해당 턴 점수 계산
        for i in range(n):
            for j in range(m):
                if died[i][j]==True:
                    temp_graph[i][j]=0
                    died[i][j]=False
                    score+=1


        #적 이동
        for i in range(n-1,0,-1):
            for j in range(m):
                temp_graph[i][j]=temp_graph[i-1][j]
        temp_graph[0]=[0]*m


        #게임 끝 판별
        temp =0
        for i in range(0,n):
            if sum(temp_graph[i])!=0:
                temp=1
                break
        if temp==0:
            break

    return score
answer = 0

for i in combinations(range(m),3):
    graph[n]=[0]*m
    graph[n][i[0]],graph[n][i[1]],graph[n][i[2]]=1,1,1
    answer = max(get_score(graph),answer)

print(answer)

byeongkeunahn 3년 전 13

궁수로부터 떨어진 거리가 같은 경우 왼쪽에 있는 것부터 처리해야 하는데, 이를 Left/Middle/Right로 나눌 때 Right 부분의 처리순서가 잘못되었습니다.

4 4 3
0 1 1 0
0 0 1 1
1 0 1 0
1 1 1 0
-> should print 8, but prints 9

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제가 문제를 잘못 이해했나요? 반례좀 알려주세요

dolgodolah 3년 전 0

byeongkeunahn 3년 전 13

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말