바닥을 밝히는 데 필요한 최소 램프 개수를 구하는 C++ 코드

문제 설명

n행 m열의 격자(grid)로 나누어진 바닥이 있다고 가정해 보겠습니다. 이 바닥 전체를 램프로 밝혀야 하는데, 램프 하나를 두 칸 사이의 경계에 놓으면 인접한 두 칸을 동시에 밝힐 수 있습니다.

램프가 세로 경계에 위치하면 왼쪽과 오른쪽 칸을 밝히고, 가로 경계에 위치하면 위쪽과 아래쪽 칸을 밝힙니다. 이때 n과 m이 주어지면, 바닥 전체를 밝히는 데 필요한 최소 램프 개수를 구해야 합니다.

예를 들어 입력이 n = 5, m = 3이라면 출력은 8이 됩니다.

풀이 접근 방법

이 문제의 핵심은 하나의 램프가 두 개의 칸을 동시에 커버할 수 있다는 점입니다. 체스판처럼 격자 칸들을 교차로 선택하면, 서로 인접한 두 칸을 하나의 램프로 묶어 밝힐 수 있습니다.

따라서 필요한 램프의 최소 개수는 전체 칸 수(n × m)를 2로 나눈 값이 되며, 전체 칸 수가 홀수인 경우에는 올림 처리를 해주어야 합니다. 이를 공식으로 표현하면 다음과 같습니다.

res := (n * m + 1) / 2
return res

C++ 구현 예시

아래 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
#define N 100
int solve(int n, int m) {
   int res = (n * m + 1) / 2;
   return res;
}
int main() {
   int n = 5, m = 3;
   cout<< solve(n, m);
   return 0;
}

입력

5, 3

출력

8

복잡도 분석

이 알고리즘은 단순한 산술 연산만 사용하므로 시간 복잡도는 O(1), 공간 복잡도 역시 O(1)입니다. 입력 크기와 무관하게 항상 일정한 시간 안에 정답을 구할 수 있다는 점이 이 풀이의 가장 큰 장점입니다.