글 읽기 - 방정식을 이용해서 k = 2^x * n + y 식으로 풀이해보았지만..

azxsdc0160 3년 전 0

놓친 조건을 계속 충족시켜주어도 틀렸다고 나오네요...

구조적으로 문제가 있는걸까요?

재귀를 이용해서 숫자를 가장 간단하게 만들어보는 방법을 시도해보았는데 택도없더군요.

혹시 놓친 논리가 있을까요...

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
typedef struct bt* tp;
typedef struct bt{
    int dis;
    int cnt;
    tp left;
    tp right;
}bt;
int counting(tp bintree, int twicecount);
int Min(int a, int b);

int main(void) {

    int result;
    int cnt = 0;
    int n, k;
    int once, twice;
    int distance, twiceCount = 0;
    int count1 = 0;
    int count2 = 0;

    scanf("%d %d", &n, &k);
    if (k <= n) {
        result = n - k;
        printf("%d", n - k);
        return 0;
    }
    tp bintree1 = NULL;
    tp bintree2 = NULL;
    bintree1 = (tp)malloc(sizeof(*bintree1)); bintree1->cnt = 0;
    bintree2 = (tp)malloc(sizeof(*bintree2)); bintree2->cnt = 0;

    once = n; twice = 2 * n;
    if (once == 0 && twice == 0) {
        count1++; count2++;
        once = 1; twice = 2;
    }

    while (1) {
        if (once <= k && twice >= k) {
            bintree1->dis = k - once;
            count1 += counting(bintree1, twiceCount) + twiceCount;
            bintree2->dis = twice - k;
            count2 += counting(bintree2, ++twiceCount) + twiceCount;
            break;
        }
        once = twice;
        twice *= 2;
        twiceCount++;
    }
        result = count1 > count2 ? count2 : count1;
        free(bintree1);
        free(bintree2);
        printf("%d", result);
        return 0;

}

int counting(tp bintree,int twicecount) {
    int divide;
    if (bintree->dis == 0)
        return 0;
    if (bintree->dis == 1)
        return 1;
    if (bintree->dis == 2)
        return 1;
    if (bintree->dis == 3)
        return 2;
    bintree->left = (tp)malloc(sizeof(*(bintree->left))); bintree->left->cnt = 0;
    bintree->right =(tp)malloc(sizeof(*(bintree->right))); bintree->right->cnt = 0;


    if ((int)pow(2, twicecount) < bintree->dis) {
        bintree->left->dis = bintree->dis % (int)pow(2, twicecount);
        bintree->right->dis = (int)pow(2, twicecount) - bintree->left->dis;
        bintree->right->cnt += 1;
        bintree->cnt += bintree->dis / (int)pow(2, twicecount) + Min(counting(bintree->left, twicecount), counting(bintree->right, twicecount));
    }
    else {
        int i = twicecount;
        while (!((int)pow(2, i) < bintree->dis && bintree->dis <= (int)pow(2, i + 1))) {
            i--;
        }
        bintree->left->dis = bintree->dis % (int)pow(2, i);
        bintree->right->dis = (int)pow(2, i + 1) - bintree->dis;
        bintree->cnt += 1 + Min(counting(bintree->left,twicecount), counting(bintree->right, twicecount));
    }
    return bintree->cnt;
}
int Min(int a, int b) {
    return a > b ? b : a;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

방정식을 이용해서 k = 2^x * n + y 식으로 풀이해보았지만..

azxsdc0160 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말