27545번 - 運河 (Canal)
JOIG 왕국의 국토는 H행 W열의 직사각형 모양의 격자판으로 나타낼 수 있다. 위에서부터 i번째 행 (1 ≤ i ≤ H), 왼쪽으로부터 j번째 열 (1 ≤ j ≤ W) 에 위치한 칸을 (i,j) 라고 한다.
각 칸에는 높이에 해당하는 양의 정수가 부여된다. (i,j)의 높이는 Ai,j 이다.
JOIG 왕국은 왕국을 종단하는 운하를 건설하려고 한다. 운하의 건설은 다음과 같이 진행된다.
임의의 칸에서 상하좌우로 인접하면서 높이가 같은 칸으로만 이동할 수 있을 때, 운하를 지나지 않으면서 이동을 반복해서 서로 방문할 수 있는 칸들의 집합을 평지라고 하자. 국토의 관리의 부담을 줄이기 위해 평지의 개수가 최소가 되게끔 운하를 건설하려고 한다.
JOIG 왕국의 지형의 정보가 주어졌을 때, 운하를 건설한 후 JOIG 왕국 내의 평지의 개수의 최솟값을 구하여라
입력은 다음과 같은 형식을 갖는다.
ㅤ
운하를 건설한 후 JOIG 왕국 내의 평지의 개수의 최솟값을 출력한다.
k = 3 인 운하를 건설한다고 하면, JOIG 왕국에는 아래와 같은 4개의 평지가 존재한다.
JOIG 왕국 내의 평지의 개수가 3개 이하가 되게끔 운하를 건설할 수 없으므로 4를 출력한다.
k = 1 인 운하를 건설하면 JOIG 왕국 내에는 8개의 평지가 존재한다. JOIG 왕국 내의 평지의 개수가 7개 이하가 되게끔 운하를 건설할 수 없으므로 8을 출력한다.
댓글을 작성하려면 로그인해야 합니다.
cinador 3년 전 2
문제
JOIG 왕국의 국토는 H행 W열의 직사각형 모양의 격자판으로 나타낼 수 있다. 위에서부터 i번째 행 (1 ≤ i ≤ H), 왼쪽으로부터 j번째 열 (1 ≤ j ≤ W) 에 위치한 칸을 (i,j) 라고 한다.
각 칸에는 높이에 해당하는 양의 정수가 부여된다. (i,j)의 높이는 Ai,j 이다.
JOIG 왕국은 왕국을 종단하는 운하를 건설하려고 한다. 운하의 건설은 다음과 같이 진행된다.
임의의 칸에서 상하좌우로 인접하면서 높이가 같은 칸으로만 이동할 수 있을 때, 운하를 지나지 않으면서 이동을 반복해서 서로 방문할 수 있는 칸들의 집합을 평지라고 하자. 국토의 관리의 부담을 줄이기 위해 평지의 개수가 최소가 되게끔 운하를 건설하려고 한다.
JOIG 왕국의 지형의 정보가 주어졌을 때, 운하를 건설한 후 JOIG 왕국 내의 평지의 개수의 최솟값을 구하여라
ㅤ
입력
입력은 다음과 같은 형식을 갖는다.
ㅤ
출력
운하를 건설한 후 JOIG 왕국 내의 평지의 개수의 최솟값을 출력한다.
ㅤ
제한
ㅤ
예제 1 설명
k = 3 인 운하를 건설한다고 하면, JOIG 왕국에는 아래와 같은 4개의 평지가 존재한다.
JOIG 왕국 내의 평지의 개수가 3개 이하가 되게끔 운하를 건설할 수 없으므로 4를 출력한다.
ㅤ
예제 2 설명
k = 1 인 운하를 건설하면 JOIG 왕국 내에는 8개의 평지가 존재한다. JOIG 왕국 내의 평지의 개수가 7개 이하가 되게끔 운하를 건설할 수 없으므로 8을 출력한다.