[C++] SWEA 1233번: 사칙연산 유효성 검사

🔗 문제

SW Expert Academy

SW Expert Academy

 

🖍 풀이

완전 이진 트리의 특성을 이용하여 풀자.

• 완전 이진 트리의 정점 개수: N
• 완전 이진 트리의 정점 번호: idx
  
  
  
  
  현재 노드 번호로 자식 노드 개수의 개수를 알 수 있다. 

 

 

 

트리로 표현했을 때 연산자가 유효할 수 있는 규칙을 찾아야 한다.

유효한 연산식 하나를 세워서 트리로 만들어 보자. 만들다 보면은 규칙이 보인다. 

유효하지 않은 사칙 연산은 규칙을 위반한다.

내가 찾은 규칙은 아래와 같고, 이 두 규칙 중 하나라도 위반하면 유효하지 않다고 판단해주었다. 

(1) N/2 미만의 노드는 숫자를 가질 수 없다.

(2) N/2 이상의 단말노드들은 연산자를 가질 수 없다 .

 

 

💾  소스

#include <iostream>

bool isNum(char c)
{
    if(c >= '0' && c<= '9')
        return true;
    
    return false;
}

int main()
{
    int T = 10;
    for (int tc = 1; tc <= T; tc++)
    {
        bool answer  = true;
        int N, idx, left, right;
        char input;
        
        std::cin >> N;
        for (int i = 0; i < N; i++)
        {
            std::cin >> idx >> input;
            
            if (idx<= N/2)
            {
                std::cin >> left;

                if(idx < (double)N/2)
                    std::cin >> right;
                    
                // 규칙 (1) 위반
                if (isNum(input))
                    answer = false;
            }
            else
            {
            	// 규칙 (2) 위반
                if (!isNum(input))
                    answer = false;
            }
        }
        
        std::cout << '#' << tc << ' '<< answer << '\\n';
    }
    return 0;
}