반응형 Round 709 썸네일형 리스트형 [Codeforces] Round #709 (div. 2) A ~ D 풀이 2021.03.21 22:20 ~ 00:35 본 라운드 참여 (performance = 1844) 테크노컵은 뭔가 항상 어려운 느낌이다... 생각보다 퍼포먼스가 나쁘지 않게는 나왔는데, 개인적으로 요즘 코포 폼이 조금 올라왔다고 생각해서 더 아쉬운 기분이 든다. A. Prison Break (*800) 모든 칸들에서 밖으로 나갈 수 있기 위해서 제거해야 하는 벽의 수의 최소를 구하는 문제이다. 답은 가로 * 세로, 즉 칸의 개수이고 대회중에는 직관적으로 빠르게 해결했다. 정확한지는 모르겠으나 증명을 하자면, 각 칸마다 해당 칸에서 시작해서 밖으로 나갈 수 있는지 없는지를 상태로 표현하고, 벽이 제거된 이웃한 칸은 하나의 칸으로 합쳐진다고 생각하자. 벽을 하나 제거했을 때 밖으로 나갈 수 없었던 2개 이상.. 이전 1 다음
