C++에서 n×m 그리드를 칠하는 최소 비용 구하기

이 튜토리얼에서는 n×m 크기의 그리드를 모두 칠할 때 드는 최소 비용을 구하는 프로그램을 다룹니다.

두 개의 정수 n과 m이 주어졌을 때, n×m 그리드 전체를 칠하는 최소 비용을 계산하는 것이 우리의 과제입니다. 여기서 한 셀을 칠하는 비용은 해당 셀에 인접한(즉, 변을 맞대고 있는) 셀 중 이미 칠해진 셀의 개수와 같다고 정의됩니다.

접근 방법

핵심 아이디어는 간단합니다. 그리드의 모든 셀이 결국 칠해지기 때문에, 서로 인접한 두 셀의 쌍은 반드시 한 번씩 비용에 기여하게 됩니다. 두 셀 중 나중에 칠해지는 순간, 이미 칠해진 이웃 셀로 인해 비용이 1만큼 발생하기 때문입니다.

따라서 최소 비용은 그리드 내부에 존재하는 인접 셀 쌍의 총 개수와 같으며, 다음과 같이 계산할 수 있습니다.

• 가로 방향 인접 쌍: 각 행에는 (m − 1)개의 가로 인접 쌍이 있고, 행이 n개이므로 n × (m − 1)
• 세로 방향 인접 쌍: 각 열에는 (n − 1)개의 세로 인접 쌍이 있고, 열이 m개이므로 m × (n − 1)

이를 정리하면 최소 비용은 다음 공식으로 표현됩니다.

최소 비용 = (n − 1) × m + (m − 1) × n

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 최소 비용을 계산하는 함수
int calc_cost(int n, int m){
    int cost = (n - 1) * m + (m - 1) * n;
    return cost;
}

int main(){
    int n = 4, m = 5;
    cout << calc_cost(n, m);
    return 0;
}

출력 결과

31

코드 설명

n = 4, m = 5인 경우를 살펴보겠습니다.

(4 − 1) × 5 + (5 − 1) × 4 = 15 + 16 = 31

즉, 4×5 그리드에는 가로 방향 인접 쌍이 15개, 세로 방향 인접 쌍이 16개 존재하므로 그리드 전체를 칠하는 데 필요한 최소 비용은 31이 됩니다.

복잡도 분석

이 방법은 단순한 산술 연산만 사용하므로 시간 복잡도는 O(1)이며, 추가로 사용되는 메모리 역시 O(1)입니다. 그리드의 크기와 무관하게 항상 일정한 시간 안에 답을 구할 수 있다는 점이 이 접근 방식의 가장 큰 장점입니다.