글 읽기 - 반례 부탁드립니다.

energyno 2년 전 0

나름 머리를 굴려서 해보았는데 오답이뜨네요..

보통 많이 나오는 반례들을 대입해봐도 답이 잘 나오는것 같은데 어디서 잘못했는지 헷갈립니다.

다른 분들 방식과 많이 달라 이해가 안가실 수 있을것 같지만 용기내어 올려봅니다.

정석적인 풀이법을 공부해봐야겠네요

import sys
import copy
times = int(sys.stdin.readline())

array = [list(map(int,sys.stdin.readline().split())) for i in range(times)]

final_area_num = [0]*102
 

for height in range(0,102):
    
    counting_arr = [ [(0,0)] + list(map(lambda x: (x+1,1) if array[i][x] > height else (x+1,0),range(times))) for i in range(times)]
    first_area = []
    cal_arr = []
    area = set()
    area2 = set()
    for i in counting_arr[0][::-1]:
        
        if i[1] != 0:
            area.add(counting_arr[0].pop())
            continue
        else:
            del counting_arr[0][-1]
            if area == set():
                continue
            else:
                first_area.append(area)
                area = set()

    index_arr = copy.deepcopy(first_area)
    first_num = len(first_area)
    for i in range(1,times):
        
        after_safe_area = []
        for k in counting_arr[i][::-1]:
            if k[1] != 0:
                area2.add(counting_arr[i].pop())
                continue
            else:
                del counting_arr[i][-1]
                if area2 == set():
                    continue
                else:
                    after_safe_area.append(area2)
                    area2 = set()
        if len(after_safe_area) != 0:
            
            for a in range(len(index_arr)):
                for b in range(len(after_safe_area)):
                    if (after_safe_area[b].isdisjoint(index_arr[a]) == True):
                        if b < len(after_safe_area)-1:
                            continue
                        else:
                            first_num += 1
                    else :
                        break
        else:
            first_num += len(index_arr)
        index_arr = copy.deepcopy(after_safe_area)

    final_area_num[height] = first_num
print(max(final_area_num))

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

문제

문제

출처

ICPC

반례 부탁드립니다.

energyno 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말