[코드포스 Practice7] E. Bear and Forgotten Tree 3

겁 먹고 패스한 문제

겁쟁이

풀어보니 그리 어려운 문제가 아니었다. 이해하는데 조금 시간이 걸리고 조건이 좀 있었을 뿐

 

 

일단 -1 조건부터 정의해줬다. 높이의 2배보다 d가 클 수 없으니 이 때는 -1을 출력하고 종료한다.

 

또 쉬운게 이게 이진트리처럼 자식의 개수가 정해져 있는게 아니다. 그래서 부모 노드에 따닥따닥 붙어있어도 된다. 

 

그래서 기본적으로 1번 노드에 자식노드를 붙이고 h와 d조건만 따로 만족시켜준다.

 

하지만 두 부분에서 빠트린 조건이 있었음.. 만약 이걸 대회중에 풀었다면 조건 못 찾아서 틀렸을 것 같다. 

 

하나는 d와 h가 같을 때

내가 푼 대로 풀면 기본적으로 1번 노드에 자식 노드가 붙어있어서 d가 4가 되고만다. 그래서 그 때는 2번 노드에 자식노드를 붙이면 d와 h가 같아질 수 있다. 

 

다음으로 h와 d가 1이고 n이 2가 아닐 때

조건이 1<=h<=d<=n-1라 노드 개수 조건 만족하겠구나 했는데 여기 허점이 있었다.

만약 h와 d가 1이면 그때는 n이 2가 되어야 한다. 아니면 조건 만족 못함.. 

#include <iostream>

using namespace std;

int main() {
    int n, d, h;
    scanf("%d %d %d", &n, &d, &h);
    
    if(d > 2*h){
        printf("-1");
        return 0;
    }
    if(d == 1 && h == 1 && n != 2){
        printf("-1");
        return 0;
    }
    
    bool isSame = false;
    int count = 2;
    
    if(d == h)
        isSame = true;
    
    for(int i = 0; i < h; i++){
        printf("%d %d\n", count -1, count);
        count++;
    }
    
    for(int i = 0; i < d-h; i++){
        if(i == 0)
            printf("1 %d\n", count);
        else
            printf("%d %d\n", count-1, count);
        count++;
    }
    
    int max = count;
    
    for(int i = 0; i <= n-max; i++){
        if(isSame)
            printf("2 %d\n", count);
        else
            printf("1 %d\n", count);
        count++;
    }
    
    return 0;
}

 

코드는 이렇게 짰다.