가수가 1분짜리 노래 a곡, 2분짜리 노래 b곡, 3분짜리 노래 c곡을 가지고 있다고 가정해 보겠습니다. 이 가수는 모든 노래를 두 개의 콘서트에 나누려고 하며, 각 노래는 반드시 정확히 하나의 콘서트에만 포함되어야 합니다. 목표는 두 콘서트 길이의 절대 차이를 최소한으로 만드는 것입니다. 여기서 콘서트의 길이란 해당 콘서트에 포함된 모든 노래 길이의 합을 의미하며, 우리는 두 콘서트 길이 차이의 최솟값을 구해야 합니다.
예를 들어 입력이 a = 2, b = 1, c = 3이라면 출력은 1이 됩니다. 첫 번째 콘서트에 1분짜리 노래 두 곡과 2분짜리 노래 한 곡, 그리고 3분짜리 노래 한 곡을 배정하고, 두 번째 콘서트에는 3분짜리 노래 두 곡을 배정할 수 있습니다. 이 경우 첫 번째 콘서트의 길이는 1 + 1 + 2 + 3 = 7분, 두 번째 콘서트의 길이는 3 + 3 = 6분이 되며, 두 값의 차이는 |7 − 6| = 1입니다.
문제 해결 접근 방식
전체 공연 시간은 a × 1 + b × 2 + c × 3 = a + 2b + 3c분입니다. 여기서 중요한 관찰은 2b가 항상 짝수이므로 전체 길이의 홀짝성(parity)은 오직 a + c의 홀짝성에 의해서만 결정된다는 점입니다.
노래의 길이가 1분, 2분, 3분으로만 구성되어 있기 때문에, 전체 길이가 짝수라면 두 콘서트의 길이를 정확히 같게 배분할 수 있어 차이가 0이 됩니다. 반면 전체 길이가 홀수라면 아무리 잘 나누어도 차이는 최소 1이 됩니다. 따라서 정답은 (a + c) % 2, 즉 a와 c의 합을 2로 나눈 나머지입니다.
return (a + c) % 2
코드에서 사용된 비트 연산자 & 1은 숫자를 2로 나눈 나머지를 구하는 것과 동일한 효과를 냅니다. 따라서 (a + c) & 1은 a + c가 짝수면 0, 홀수면 1을 반환합니다.
C++ 구현 예시
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include<bits/stdc++.h>
using namespace std;
int solve(int a, int b, int c){
return ((a + c) & 1);
}
int main(){
int a = 2;
int b = 1;
int c = 3;
cout << solve(a, b, c) << endl;
}입력
2, 1, 3
출력
1
a = 2, c = 3일 때 a + c = 5이고 5는 홀수이므로 함수는 1을 반환합니다. 이는 앞서 살펴본 예시의 결과와 일치합니다. 이 풀이는 단순한 덧셈과 나머지 연산만 수행하므로 시간 복잡도는 O(1)로 매우 효율적입니다.