c++문제풀이 도움주시면 감사드리겠습니답

조회수 1205회

백준 문제를 풀다가 막히는 부분이 있어서 질문드립니다 https://www.acmicpc.net/problem/12779(문제 원본) 분자가 주어진 범위안의 제곱수이고 분모가 주어진 범위인 문제입니다 여기까지는 정상적으로 돌아갔는데 조건중 '기약분수형태'로 표현하라는 구문이 있어서 분자와 분모를 각 최대공약수로 나누어주는 함수를 추가하였더니 엉뚱한 값이 출력되는데 어디가 문제인지 알려주시면 정말 감사드리겠습니다.

//
#include <iostream>
#include <cmath>
using namespace std;
unsigned int findpow(unsigned int m);
unsigned int gcd(unsigned int q, unsigned int p);
int main(){
    unsigned int a, b;//0~(2의30승의제곱)
    cin >> a >> b;
    if (findpow(b) - findpow(a) == 0) { cout << '0'; }
    else {
    cout << (findpow(b) - findpow(a))/gcd(findpow(b), findpow(a)) << '/' << (b - a)/gcd(findpow(b), findpow(a));
}return 0;
}
unsigned int findpow(unsigned int m) {//제곱수구하기
    for (int i = 1; i < pow(2, 30); i++) {
        if (m < pow(i, 2)) {
            break; 
        }return (i - 1);
    }
}
unsigned int gcd(unsigned int q, unsigned int p) {
        unsigned int k = 0;
        while (p != 0){ 
            k = q % p;
            q = p;
            p = k;
        }
        return p;
}

3 답변

  • 좋아요

    0

    싫어요
    채택 취소하기

    unsigned int gcd(q, p)가 수상합니다. while 무한루프로 최대공약수를 찾는 거라면 대충 이렇게 하시면 될텐데요? (제가 C를 몰라서 파이썬으로 알고리즘만 설명합니다.)

    def gcd(a, b) :
        # 공약수 후보를 선정한다.
        # 재수가 좋으면 둘중 더 작은 수로 더 큰 수가 나누어 떨어질 수 있으니 일단 그놈을 후보로 잡는다.
        c = a if a < b else b
        # 지금 공약수 후보를 가지고 두 수를 mod 연산해 본다.
        while a % c != 0 or b % c != 0 :
            # 둘 중 하나라도 나누어 떨어지지 않는다면 지금의 후보에서 1을 빼서 그걸로 다시 해 본다.
            c = c - 1
        # 둘 다 나누어 떨어졌다면 지금 공약수 후보가 실제 최대공약수다.
        return c
    
    # 야! 너두 최대공약수 구할 수 있어!
    print(gcd(7, 3))
    print(gcd(24, 18))
    print(gcd(16*17, 12*17))
    

    도움이 되었으면 좋겠네요.

    • 답변 감사합니다 김동현 2019.6.2 22:10
  • 엽토군님 코드를 c로 그대로 옮겨드립니다.

    • gcd.cpp
    unsigned int gcd(unsigned int a, unsigned int b) {
       int c = a < b ? a : b;
       while((a % c != 0) || (b % c != 0)) { c -= 1; }
       return c;
    }
    

    나머지 이것저것 손봤습니다.

    • cling(c++ 인터프리터입니다.)
    [cling]$ .L main.cpp
    [cling]$ main()
    1/3
    
    
    • main.cpp
    #include <iostream>
    #include <cmath>
    
    using namespace std;
    
    unsigned int findpow(unsigned int m);
    bool issquare(unsigned int n);
    unsigned int gcd(unsigned int a, unsigned int b);
    
    unsigned int findpow(unsigned int m) {
        for (int i = 1; i < pow(2, 30); i++) {
            if (m == pow(i, 2)) {
                return i; 
            } 
        }
    
        return 0;
    }
    
    // 제곱수 판별
    bool issquare(unsigned int n) {
       return pow(pow(n, 0.5), 2) == n;
    }
    
    unsigned int gcd(unsigned int a, unsigned int b) {
       int c = a < b ? a : b;
       while((a % c != 0) || (b % c != 0)) { c -= 1; }
       return c;
    }
    
    int main() {
       int a = 1, b = 4;
       if(issquare(a) && issquare(b)) {
          cout << int((findpow(b) - findpow(a))/gcd(findpow(b), findpow(a))) << "/" << int((b - a)/gcd(findpow(b), findpow(a))) << endl;
       }else{
          cout << '0' <<endl;
       }
       return 0;
    }
    
  • unsigned int findpow(unsigned int m) {//제곱수구하기
        for (int i = 1; i < pow(2, 30); i++) {
            if (m < pow(i, 2)) {
                break; 
            }
        }
        return (i - 1);
    }
    

    그리고, 약분을 하려면, 분자와 분모의 공약수로 나눠야 하는데, 이상한 공약수를 구해서 나누고 있어요.

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)