C++로 세 원자의 원자가를 이용해 하나의 분자를 만들 수 있는지 판별하기

원자가(valence number)란 한 원자가 다른 원자들과 몇 개의 결합을 이루어야 하는지를 나타내는 수입니다. 문제에서는 세 원자의 원자가가 주어지며, 이 세 원자가 서로 결합하여 하나의 분자를 형성할 수 있는지 판별해야 합니다. 단, 원자들은 서로 여러 개의 결합을 동시에 맺을 수 있다는 점에 유의해야 합니다.

예를 들어 세 원자의 원자가가 각각 2, 4, 2라고 해 보겠습니다. 이 경우 결합은 아래와 같이 배치될 수 있으므로 정답은 YES입니다.

1 – 2, 1 – 2, 2 – 3, 2 – 3

문제 풀이 접근 방식

세 원자의 원자가를 각각 a, b, c라고 하고, 편의상 c가 세 값 중 가장 크다고 가정합니다. 이때 세 원자가 분자를 형성할 수 없는 경우는 다음 두 가지뿐입니다.

• a + b + c가 홀수인 경우: 하나의 결합이 생길 때마다 관련된 두 원자의 원자가가 각각 1씩 감소합니다. 따라서 모든 결합이 완성되려면 원자가의 총합이 반드시 짝수여야 합니다. 총합이 홀수라면 어떻게 배치하더라도 남는 결합이 생깁니다.
• a + b < c인 경우: 나머지 두 원자가 제공할 수 있는 결합의 수보다 가장 큰 원자의 원자가가 더 크기 때문에, 그 원자의 결합 요구량을 모두 채울 수 없습니다. 즉, 사용되지 못한 연결이 남게 됩니다.

위 두 조건에 해당하지 않으면 세 원자는 반드시 하나의 분자를 형성할 수 있으며, 이 판별은 상수 시간(O(1)) 안에 처리됩니다.

예제 코드

#include<iostream>
using namespace std;

bool canMakeMolecule(int a, int b, int c) {
    // 총합이 홀수이거나, 가장 큰 값이 나머지 합보다 크면 불가능
    if ((a + b + c) % 2 != 0 || a + b < c)
        return false;
    else
        return true;
}

int main() {
    int a = 2, b = 4, c = 2;
    if (canMakeMolecule(a, b, c)) {
        cout << "They can form Molecule";
    } else {
        cout << "They can not form Molecule";
    }
}

실행 결과

They can form Molecule

위 예제에서 원자가는 2, 4, 2입니다. 총합은 8로 짝수이고, 가장 큰 값 4가 나머지 두 값의 합 4보다 작거나 같으므로, 세 원자는 성공적으로 하나의 분자를 형성할 수 있습니다.