현대 매직쇼에서는 마술사들이 벽을 통과하는 종목은 인기 종목이다. 이는 마술사가 미리 디자인되어 있는 스테이지에서 여러개의 벽을 통과한다. 벽은 격자 모양에 놓여진다. 보기 1 에서 보여지고 있다. 이 그림은 평면도 있다.
모든 벽은 폭은 같고 길이가 다르다. 벽들은 겹치지 않는다고 하자. 관객이 열을 선택하면 마술사는 제일 위 열에서 시작해서 모든 벽을 통과해서 제일 아래까지 도달하는 것이다. 그가 가지고 있는 에너지 가 k 이면 , k 개 보다 더 많은 벽을 통과하는 경우 이 쇼는 실패하게 된다.
그림 1 과 같은 모양에서는 k = 3 이면 6 번 컬럼를 제외하고는 모든 열에서 아래까지 도달할 수 있다. 마술사의 에너지 값 k 와 스테이지가 주어질 때 우리는 어떤 컬럼에서 시작하더라도 아래로 빠져 나오도록 최소한의 벽을 치우고자 한다.(번역자 주: 벽의 일부분만 제거될 수은 없고 전체 벽을 치워야 한다.) 제거될 최소 벽 수를 구하는 게 문제이다.
입력 2 3 1 2 0 4 0 0 1 1 1 1 2 2 2 7 3 0 0 3 0 6 1 8 1 2 3 6 3 4 4 6 4 0 5 1 5 5 6 7 6 1 7 3 7 출력 1 1
출처:Tehran 2002 Preliminary