'개발/문제풀이' 카테고리의 글 목록

개발/문제풀이

Code. 프로젝트 오일러. KR 16번. C++14

ordi2017. 1. 30. 11:18

Project Euler

Problem 16

Power Digit Sum

성능 시간 : 0.806ms

// '17.01.30.
// 하드 코딩
// 큰 수 처리하기

#include <iostream>
#include <vector>
using namespace std;

long long sumAllDigit(const vector<int> &vDigit)
{
	long long sum = 0;
	const int TEN = 10;
	
	for (auto i : vDigit)
	{
		while (i > 0)
		{
			sum += i % TEN;
			i /= TEN;
		}
	}
	
	return sum;
}

void multiplyDigit(vector<int> &vDigit, int operand)
{
	int upper = 0;
	const int DIGIT = 10000;
	
	for (auto &i: vDigit)
	{
		i *= operand;
		i += upper;
		upper = i / DIGIT;
		i %= DIGIT;
	}
	
	if (upper > 0)
		vDigit.push_back(upper);
}

void printDigit(const vector<int> &vDigit)
{
	for (int i = vDigit.size() - 1; i >= 0; i--)
		cout << vDigit[i];
	cout << endl;
}

int main()
{
	vector<int> vDigit {2};
	const int TWO = 2;
	const int LIMIT = 1000;
	
	clock_t start = clock(); // 실행시간 분석
	
	for (int i = 1; i < LIMIT; i++) {
		multiplyDigit(vDigit, TWO);
	}
	
	printDigit(vDigit);
	cout << "sum : " << sumAllDigit(vDigit) << endl;
	
	clock_t end = clock(); // 실행시간 분석
	cout << (double) (end - start) / CLOCKS_PER_SEC * 1000 << " ms" << endl; // 실행시간 출력
}

저작자표시 비영리

'개발 > 문제풀이' 카테고리의 다른 글

Code. 프로젝트 오일러. KR 14번. C++ (0)	2016.10.09
Code. 프로젝트 오일러. KR 13번. C++ (0)	2016.10.09
Code. 프로젝트 오일러. KR 12번. C++ (0)	2016.10.03
Code. 프로젝트 오일러. KR 11번. C++ (0)	2016.10.01
Code. 프로젝트 오일러. KR 10번. C++ (0)	2016.10.01

개발/문제풀이

Code. 프로젝트 오일러. KR 14번. C++

ordi2016. 10. 9. 19:26

'개발 > 문제풀이' 카테고리의 다른 글

Code. 프로젝트 오일러. KR 16번. C++14 (0)	2017.01.30
Code. 프로젝트 오일러. KR 13번. C++ (0)	2016.10.09
Code. 프로젝트 오일러. KR 12번. C++ (0)	2016.10.03
Code. 프로젝트 오일러. KR 11번. C++ (0)	2016.10.01
Code. 프로젝트 오일러. KR 10번. C++ (0)	2016.10.01

개발/문제풀이

Code. 프로젝트 오일러. KR 13번. C++

ordi2016. 10. 9. 14:46

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s =  "37107287533902102798797998220837590246510135740250"
                "46376937677490009712648124896970078050417018260538"
                "74324986199524741059474233309513058123726617309629"
                "91942213363574161572522430563301811072406154908250"
                "23067588207539346171171980310421047513778063246676"
                "89261670696623633820136378418383684178734361726757"
                "28112879812849979408065481931592621691275889832738"
                "44274228917432520321923589422876796487670272189318"
                "47451445736001306439091167216856844588711603153276"
                "70386486105843025439939619828917593665686757934951"
                "62176457141856560629502157223196586755079324193331"
                "64906352462741904929101432445813822663347944758178"
                "92575867718337217661963751590579239728245598838407"
                "58203565325359399008402633568948830189458628227828"
                "80181199384826282014278194139940567587151170094390"
                "35398664372827112653829987240784473053190104293586"
                "86515506006295864861532075273371959191420517255829"
                "71693888707715466499115593487603532921714970056938"
                "54370070576826684624621495650076471787294438377604"
                "53282654108756828443191190634694037855217779295145"
                "36123272525000296071075082563815656710885258350721"
                "45876576172410976447339110607218265236877223636045"
                "17423706905851860660448207621209813287860733969412"
                "81142660418086830619328460811191061556940512689692"
                "51934325451728388641918047049293215058642563049483"
                "62467221648435076201727918039944693004732956340691"
                "15732444386908125794514089057706229429197107928209"
                "55037687525678773091862540744969844508330393682126"
                "18336384825330154686196124348767681297534375946515"
                "80386287592878490201521685554828717201219257766954"
                "78182833757993103614740356856449095527097864797581"
                "16726320100436897842553539920931837441497806860984"
                "48403098129077791799088218795327364475675590848030"
                "87086987551392711854517078544161852424320693150332"
                "59959406895756536782107074926966537676326235447210"
                "69793950679652694742597709739166693763042633987085"
                "41052684708299085211399427365734116182760315001271"
                "65378607361501080857009149939512557028198746004375"
                "35829035317434717326932123578154982629742552737307"
                "94953759765105305946966067683156574377167401875275"
                "88902802571733229619176668713819931811048770190271"
                "25267680276078003013678680992525463401061632866526"
                "36270218540497705585629946580636237993140746255962"
                "24074486908231174977792365466257246923322810917141"
                "91430288197103288597806669760892938638285025333403"
                "34413065578016127815921815005561868836468420090470"
                "23053081172816430487623791969842487255036638784583"
                "11487696932154902810424020138335124462181441773470"
                "63783299490636259666498587618221225225512486764533"
                "67720186971698544312419572409913959008952310058822"
                "95548255300263520781532296796249481641953868218774"
                "76085327132285723110424803456124867697064507995236"
                "37774242535411291684276865538926205024910326572967"
                "23701913275725675285653248258265463092207058596522"
                "29798860272258331913126375147341994889534765745501"
                "18495701454879288984856827726077713721403798879715"
                "38298203783031473527721580348144513491373226651381"
                "34829543829199918180278916522431027392251122869539"
                "40957953066405232632538044100059654939159879593635"
                "29746152185502371307642255121183693803580388584903"
                "41698116222072977186158236678424689157993532961922"
                "62467957194401269043877107275048102390895523597457"
                "23189706772547915061505504953922979530901129967519"
                "86188088225875314529584099251203829009407770775672"
                "11306739708304724483816533873502340845647058077308"
                "82959174767140363198008187129011875491310547126581"
                "97623331044818386269515456334926366572897563400500"
                "42846280183517070527831839425882145521227251250327"
                "55121603546981200581762165212827652751691296897789"
                "32238195734329339946437501907836945765883352399886"
                "75506164965184775180738168837861091527357929701337"
                "62177842752192623401942399639168044983993173312731"
                "32924185707147349566916674687634660915035914677504"
                "99518671430235219628894890102423325116913619626622"
                "73267460800591547471830798392868535206946944540724"
                "76841822524674417161514036427982273348055556214818"
                "97142617910342598647204516893989422179826088076852"
                "87783646182799346313767754307809363333018982642090"
                "10848802521674670883215120185883543223812876952786"
                "71329612474782464538636993009049310363619763878039"
                "62184073572399794223406235393808339651327408011116"
                "66627891981488087797941876876144230030984490851411"
                "60661826293682836764744779239180335110989069790714"
                "85786944089552990653640447425576083659976645795096"
                "66024396409905389607120198219976047599490197230297"
                "64913982680032973156037120041377903785566085089252"
                "16730939319872750275468906903707539413042652315011"
                "94809377245048795150954100921645863754710598436791"
                "78639167021187492431995700641917969777599028300699"
                "15368713711936614952811305876380278410754449733078"
                "40789923115535562561142322423255033685442488917353"
                "44889911501440648020369068063960672322193204149535"
                "41503128880339536053299340368006977710650566631954"
                "81234880673210146739058568557934581403627822703280"
                "82616570773948327592232845941706525094512325230608"
                "22918802058777319719839450180888072429661980811197"
                "77158542502016545090413245809786882778948721859617"
                "72107838435069186155435662884062257473692284509516"
                "20849603980134001723930671666823555245252804609722"
                "53503534226472524250874054075591789781264330331690";
    
    const int MOD_NUM = 100000; // 다섯자리만을 남기기 위한 수
    const int HUNDRED = 100;
    const int FIFTY   = 50;
    const int FIFTYFIVE   = 45;
    const int FIVE    = 5;
    const int ZERO    = 0;
    
    string str_num = s.substr(ZERO, FIFTY);
    int over = 0;
    
    for (int i = 1; i < HUNDRED; i++)
    {
        string str_temp = s.substr(FIFTY * i, FIFTY);
        int upper = 0;  // 올림
        
        // 50자리를 바로 변환하면 오버플로우 발생
        // 따라서 5자리씩 뽑아서 계산.
        for (int pos = FIFTYFIVE; pos >= ZERO; pos -= FIVE)
        {
            int temp = stoi( str_num.substr(pos, FIVE) );
            temp += stoi( str_temp.substr(pos, FIVE) );
            temp += upper;
            
            upper = 0;
            
            if (temp >= MOD_NUM)
            {
                upper = 1;
                temp %= MOD_NUM;
            }
            
            // temp가 5자리가 아닐 경우가 있음
            // 그때는 앞에 0을 추가해서 5자리로 만들어 줘야함.
            string check_str = to_string(temp);
            if (check_str.length() < FIVE)
            {
                int limit = FIVE - check_str.length();
                for (int j = 0; j < limit; j++)
                    check_str = "0" + check_str;
            }
            
            str_num.replace(pos, FIVE, check_str);
        }
        
        if (upper > ZERO) over++;
        
        cout << to_string(over) << "\t" << str_num << endl;
    }
    
    cout << "\t=>" << to_string(over) << str_num.substr(0, 10 - to_string(over).length()) << endl;
    
    return 0;
}

'개발 > 문제풀이' 카테고리의 다른 글

Code. 프로젝트 오일러. KR 16번. C++14 (0)	2017.01.30
Code. 프로젝트 오일러. KR 14번. C++ (0)	2016.10.09
Code. 프로젝트 오일러. KR 12번. C++ (0)	2016.10.03
Code. 프로젝트 오일러. KR 11번. C++ (0)	2016.10.01
Code. 프로젝트 오일러. KR 10번. C++ (0)	2016.10.01

개발/문제풀이

Code. 프로젝트 오일러. KR 12번. C++

ordi2016. 10. 3. 20:12

소스코드가... 클래스 연습겸 만들다보니 길어졌습니다...

#include <iostream>
#include <vector>
using namespace std;

class Factor {
private:
    int num;
    int cnt;
    
public:
    Factor(int n = 1) {
        num = n;
        cnt = 1;
    };
    void addCnt() {
        cnt++;
    };
    int getCnt() {
        return cnt;  
    };
};

typedef vector<Factor> FactVector;

class PrimeDivisor {
private :
    int targetNum;
    int numOfFactor;
    FactVector v_pFactor;
    
    void FindFactor() {
        int temp = targetNum;
        
        for (int i = 2; temp > 1; i++)
        {
            if (temp % i == 0)
            {
                temp /= i;
                v_pFactor.push_back( Factor(i) );
                int index = v_pFactor.size() - 1;
                
                while (temp % i == 0) {
                    temp /= i;
                    v_pFactor[index].addCnt();
                }
            }
        }
        
        numOfFactor = 1;
        int limit = v_pFactor.size();
        
        for (int i = 0; i < limit; i++) {
            numOfFactor *= v_pFactor[i].getCnt() + 1;
        }

};
    
public :
    PrimeDivisor(int target) {
        targetNum = target;
        FindFactor();
    };
    
    int getTheNumOfFactor() {
        return numOfFactor;
    };
};

int main()
{
    int i = 1;
    int sum = 1;
    
    while (true)
    {
        i++;
        sum += i;
        PrimeDivisor pd(sum);
        
        cout << sum << "\t" << pd.getTheNumOfFactor() << endl; 
        
        if (pd.getTheNumOfFactor() >= 500)
            break;
        
    }
    
    return 0;
}

'개발 > 문제풀이' 카테고리의 다른 글

Code. 프로젝트 오일러. KR 14번. C++ (0)	2016.10.09
Code. 프로젝트 오일러. KR 13번. C++ (0)	2016.10.09
Code. 프로젝트 오일러. KR 11번. C++ (0)	2016.10.01
Code. 프로젝트 오일러. KR 10번. C++ (0)	2016.10.01
Code. 프로젝트 오일러. KR 9번. C++ (0)	2016.09.28

개발/문제풀이

Code. 프로젝트 오일러. KR 11번. C++

ordi2016. 10. 1. 17:31

#include <iostream>
using namespace std;

#define myint   long long
#define SIZE    20
#define LIMIT   4

bool    checkOutOfBound(int x, int y);
myint   multi4ElementOnDir(int arr[SIZE][SIZE], int dir, int x, int y);

int main()
{
    const int size = SIZE;
    myint max_mul = 0;
    int arr[SIZE][SIZE] =
    {
        {8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8},
        {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0},
        {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65},
        {52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91},
        {22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
        {24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
        {32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
        {67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21},
        {24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
        {21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95},
        {78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92},
        {16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57},
        {86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
        {19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40},
        {04, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
        {88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
        {4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36},
        {20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16},
        {20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54},
        {1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48}
    };
    
    for (int y = 0; y < size; y++)
        for (int x = 0; x < size; x++)
            for (int dir = 0; dir <= 3; dir++)
            {
                myint cur_mul = multi4ElementOnDir(arr, dir, x, y);
                if ( max_mul < cur_mul )
                {
                    max_mul = cur_mul;
                    cout << max_mul << "\t" << x << "\t" << y << endl;
                }
            }
}

bool checkOutOfBound(int x, int y)
{
    
    if (x >= SIZE || y >= SIZE || x < 0 || y < 0)
        return false;
    return true;
}

myint multi4ElementOnDir(int arr[SIZE][SIZE], int dir, int x, int y)
{
    myint mul = 1;
    const int dir_x[LIMIT] = {-1, 0, 1, 1};
    const int dir_y[LIMIT] = {1, 1, 1, 0};
    
    for (int i = 0 ; i < LIMIT; i++)
    {
        if (checkOutOfBound(x, y) == false)
            return -1;
            
        mul *= arr[y][x];
        x += dir_x[dir];
        y += dir_y[dir];
    }
    
    return mul;
}

'개발 > 문제풀이' 카테고리의 다른 글

Code. 프로젝트 오일러. KR 13번. C++ (0)	2016.10.09
Code. 프로젝트 오일러. KR 12번. C++ (0)	2016.10.03
Code. 프로젝트 오일러. KR 10번. C++ (0)	2016.10.01
Code. 프로젝트 오일러. KR 9번. C++ (0)	2016.09.28
Code. 프로젝트 오일러. KR 8번. C++ (0)	2016.09.25

개발/문제풀이

Code. 프로젝트 오일러. KR 10번. C++

ordi2016. 10. 1. 16:41

'개발 > 문제풀이' 카테고리의 다른 글

Code. 프로젝트 오일러. KR 12번. C++ (0)	2016.10.03
Code. 프로젝트 오일러. KR 11번. C++ (0)	2016.10.01
Code. 프로젝트 오일러. KR 9번. C++ (0)	2016.09.28
Code. 프로젝트 오일러. KR 8번. C++ (0)	2016.09.25
Code. 프로젝트 오일러. KR 7번. C++ (0)	2016.09.25

개발/문제풀이

Code. 프로젝트 오일러. KR 9번. C++

ordi2016. 9. 28. 19:56

'개발 > 문제풀이' 카테고리의 다른 글

Code. 프로젝트 오일러. KR 11번. C++ (0)	2016.10.01
Code. 프로젝트 오일러. KR 10번. C++ (0)	2016.10.01
Code. 프로젝트 오일러. KR 8번. C++ (0)	2016.09.25
Code. 프로젝트 오일러. KR 7번. C++ (0)	2016.09.25
Code. 프로젝트 오일러. KR 6번. C++ (0)	2016.09.25

개발/문제풀이

Code. 프로젝트 오일러. KR 8번. C++

ordi2016. 9. 25. 15:37

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string str;
    str.append("73167176531330624919225119674426574742355349194934");
    str.append("96983520312774506326239578318016984801869478851843");
    str.append("85861560789112949495459501737958331952853208805511");
    str.append("12540698747158523863050715693290963295227443043557");
    str.append("66896648950445244523161731856403098711121722383113");
    str.append("62229893423380308135336276614282806444486645238749");
    str.append("30358907296290491560440772390713810515859307960866");
    str.append("70172427121883998797908792274921901699720888093776");
    str.append("65727333001053367881220235421809751254540594752243");
    str.append("52584907711670556013604839586446706324415722155397");
    str.append("53697817977846174064955149290862569321978468622482");
    str.append("83972241375657056057490261407972968652414535100474");
    str.append("82166370484403199890008895243450658541227588666881");
    str.append("16427171479924442928230863465674813919123162824586");
    str.append("17866458359124566529476545682848912883142607690042");
    str.append("24219022671055626321111109370544217506941658960408");
    str.append("07198403850962455444362981230987879927244284909188");
    str.append("84580156166097919133875499200524063689912560717606");
    str.append("05886116467109405077541002256983155200055935729725");
    str.append("71636269561882670428252483600823257530420752963450");
    
    const int TEN = 10;
    const int FIVE = 5;
    const int LIMIT = str.size() - FIVE;
    int max = 0;
    
    for (int i = 0; i <= LIMIT; i++)
    {
        int num = stoi( str.substr(i, FIVE) );
        int temp = num;
        int sum = 1;
        
        for (int j = 0; j < FIVE; j++)
        {
            sum *= temp % TEN;
            temp /= TEN;
        }
        
        if (max < sum)
        {
            max = sum;
            cout << num << '\t' << max << endl;
        }
    }
    
    return 0;
}

'개발 > 문제풀이' 카테고리의 다른 글

Code. 프로젝트 오일러. KR 10번. C++ (0)	2016.10.01
Code. 프로젝트 오일러. KR 9번. C++ (0)	2016.09.28
Code. 프로젝트 오일러. KR 7번. C++ (0)	2016.09.25
Code. 프로젝트 오일러. KR 6번. C++ (0)	2016.09.25
Code. 프로젝트 오일러. KR 5번. C++ (0)	2016.09.25

개발/문제풀이

Code. 프로젝트 오일러. KR 7번. C++

ordi2016. 9. 25. 14:56

'개발 > 문제풀이' 카테고리의 다른 글

Code. 프로젝트 오일러. KR 9번. C++ (0)	2016.09.28
Code. 프로젝트 오일러. KR 8번. C++ (0)	2016.09.25
Code. 프로젝트 오일러. KR 6번. C++ (0)	2016.09.25
Code. 프로젝트 오일러. KR 5번. C++ (0)	2016.09.25
Code. 프로젝트 오일러. KR 4번. C++ (0)	2016.09.25

개발/문제풀이

Code. 프로젝트 오일러. KR 6번. C++

ordi2016. 9. 25. 14:33

'개발 > 문제풀이' 카테고리의 다른 글

Code. 프로젝트 오일러. KR 8번. C++ (0)	2016.09.25
Code. 프로젝트 오일러. KR 7번. C++ (0)	2016.09.25
Code. 프로젝트 오일러. KR 5번. C++ (0)	2016.09.25
Code. 프로젝트 오일러. KR 4번. C++ (0)	2016.09.25
Code. 프로젝트 오일러. KR 3번. C++ (0)	2016.09.24

싶어그래

'개발 > 문제풀이' 카테고리의 다른 글

'개발 > 문제풀이' 카테고리의 다른 글

'개발 > 문제풀이' 카테고리의 다른 글

'개발 > 문제풀이' 카테고리의 다른 글

'개발 > 문제풀이' 카테고리의 다른 글

'개발 > 문제풀이' 카테고리의 다른 글

'개발 > 문제풀이' 카테고리의 다른 글

'개발 > 문제풀이' 카테고리의 다른 글

'개발 > 문제풀이' 카테고리의 다른 글

'개발 > 문제풀이' 카테고리의 다른 글

티스토리툴바