매초리의 생활공간

[25/C++] 피보나치 수열에서 처음으로 1000자리가 되는 항은 몇 번째?

[25번 문제] 피보나치 수열은 아래와 같은 점화식으로 정의됩니다.Fn = Fn-1 + Fn-2 (단, F1 = 1, F2 = 1).이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다.F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34 F10 = 55 F11 = 89 F12 = 144수열의 값은 F12에서 처음으로 3자리가 됩니다.피보나치 수열에서 값이 처음으로 1000자리가 되는 것은 몇번째 항입니까?[ 번역링크 / 원본링크 ][코드] 기존에 vector와 capacity 를 사용하면서 배열범위 초과 오류가 뜨는지 영문을 몰랐는데.....capacity로 벡터의 크기를 확인하는게 아니라 size로 확인해야했었다..1234..

Solution/Project Euler 2018. 5. 29. 02:22

[24/C++] 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 1,000,000번째 사전식 순열은?

[24번 문제] 어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 3124는 숫자 1, 2, 3, 4로 만들 수 있는 순열 중 하나입니다.이렇게 만들 수 있는 모든 순열을 숫자나 문자 순으로 늘어놓은 것을 사전식(lexicographic) 순서라고 합니다. 0, 1, 2로 만들 수 있는 사전식 순열은 다음과 같습니다.012 021 102 120 201 2100, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열에서 1,000,000번째는 무엇입니까?[ 번역링크 / 원본링크 ][코드] 12345678910111213141516171819202122232425#include "stdafx.h"#include #include #include using namespac..

Solution/Project Euler 2018. 5. 28. 20:41

[23/C++] 두 초과수의 합으로 나타낼 수 없는 모든 양의 정수의 합은?

[23번 문제] 자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다. 예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다. 또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 초과수라고 합니다.12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 초과수 중에서는 가장 작습니다. 따라서 초과수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다.해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 초과수의 합으로 표현 가능함을 보일 수가 있습니다. 두 초과수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 ..

Solution/Project Euler 2018. 5. 28. 15:31

[22/C++] 영문 이름 점수 합계 구하기

[22번 문제] 여기 5천개 이상의 영문 이름들이 들어있는 46KB짜리 텍스트 파일 names.txt 이 있습니다 (우클릭해서 다운로드 받으세요).이제 각 이름에 대해서 아래와 같은 방법으로 점수를 매기고자 합니다.먼저 모든 이름을 알파벳 순으로 정렬합니다.각 이름에 대해서, 그 이름을 이루는 알파벳에 해당하는 숫자(A=1, B=2, ..., Z=26)를 모두 더합니다.여기에 이 이름의 순번을 곱합니다.예를 들어 "COLIN"의 경우, 알파벳에 해당하는 숫자는 3, 15, 12, 9, 14이므로 합이 53, 그리고 정렬했을 때 938번째에 오므로 최종 점수는 938 × 53 = 49714가 됩니다.names.txt에 들어있는 모든 이름의 점수를 계산해서 더하면 얼마입니까?[ 번역링크 / 원본링크 ][코드..

Solution/Project Euler 2018. 5. 26. 17:07

[21/C++] 10000 이하 모든 친화수(우애수)의 합은?

[21번 문제] n의 약수들 중에서 자신을 제외한 것의 합을 d(n)으로 정의했을 때, 서로 다른 두 정수 a, b에 대하여 d(a) = b 이고 d(b) = a 이면 a, b는 친화쌍이라 하고 a와 b를 각각 친화수(우애수)라고 합니다.예를 들어 220의 약수는 자신을 제외하면 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 이므로 그 합은 d(220) = 284 입니다. 또 284의 약수는 자신을 제외하면 1, 2, 4, 71, 142 이므로 d(284) = 220 입니다. 따라서 220과 284는 친화쌍이 됩니다.10000 이하의 친화수들을 모두 찾아서 그 합을 구하세요.[ 번역링크 / 원본링크 ][코드] 123456789101112131415161718192021222324..

Solution/Project Euler 2018. 5. 26. 16:09

[20/C++] 100! 의 자리수를 모두 더하면?

[20번 문제] n! 이라는 표기법은 n × (n − 1) × ... × 3 × 2 × 1을 뜻합니다.예를 들자면 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 이 되는데, 여기서 10!의 각 자리수를 더해 보면 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 입니다.100! 의 자리수를 모두 더하면 얼마입니까?[ 번역링크 / 원본링크 ][코드] 오류를 아직 잡지못했다... 당장은 뭐가오류인지 못찾아서 보류 자릿수가 들어갈 배열이 모자라서 결과가 제대로 나오지 않았다.. 123456789101112131415161718192021222324252627282930313233343536#include "stdafx.h"#include #include using namespa..

Solution/Project Euler 2018. 5. 26. 13:17

[19/C++] 20세기에서, 매월 1일이 일요일인 경우는 몇 번?

[19번 문제] 다음은 달력에 관한 몇 가지 일반적인 정보입니다 (필요한 경우 좀 더 연구를 해 보셔도 좋습니다).1900년 1월 1일은 월요일이다.4월, 6월, 9월, 11월은 30일까지 있고, 1월, 3월, 5월, 7월, 8월, 10월, 12월은 31일까지 있다.2월은 28일이지만, 윤년에는 29일까지 있다.윤년은 연도를 4로 나누어 떨어지는 해를 말한다. 하지만 400으로 나누어 떨어지지 않는 매 100년째는 윤년이 아니며, 400으로 나누어 떨어지면 윤년이다20세기 (1901년 1월 1일 ~ 2000년 12월 31일) 에서, 매월 1일이 일요일인 경우는 총 몇 번입니까?[ 번역링크 / 원본링크 ][코드] 1234567891011121314151617181920212223242526272829#in..

Solution/Project Euler 2018. 5. 26. 11:45

[18/C++] 삼각형을 따라 내려가면서 합이 최대가 되는 경로 찾기

[18번 문제] 다음과 같이 삼각형 모양으로 숫자를 배열했습니다.3 7 4 2 4 6 8 5 9 3삼각형의 꼭대기부터 아래쪽으로 인접한 숫자를 찾아 내려가면서 합을 구하면, 위의 그림처럼 3 + 7 + 4 + 9 = 23 이 가장 큰 합을 갖는 경로가 됩니다.다음 삼각형에서 합이 최대가 되는 경로를 찾아서 그 합을 구하세요.75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 ..

Solution/Project Euler 2018. 5. 26. 10:38

[17/C++] 1부터 1000까지 영어로 썼을 때 사용된 글자의 개수는?

[17번 문제] 1부터 5까지의 숫자를 영어로 쓰면 one, two, three, four, five 이고, 각 단어의 길이를 더하면 3 + 3 + 5 + 4 + 4 = 19 이므로 사용된 글자는 모두 19개입니다.1부터 1,000까지 영어로 썼을 때는 모두 몇 개의 글자를 사용해야 할까요?참고: 빈 칸이나 하이픈('-')은 셈에서 제외하며, 단어 사이의 and 는 셈에 넣습니다. 예를 들어 342를 영어로 쓰면 three hundred and forty-two 가 되어서 23 글자, 115 = one hundred and fifteen 의 경우에는 20 글자가 됩니다.[ 번역링크 / 원본링크 ][코드] 12345678910111213141516171819202122232425262728293031323..

Solution/Project Euler 2018. 5. 25. 23:00

[16/C++] 2^1000의 각 자리수를 모두 더하면?

[16번 문제] 215 = 32768 의 각 자리수를 더하면 3 + 2 + 7 + 6 + 8 = 26 입니다.21000의 각 자리수를 모두 더하면 얼마입니까?[ 번역링크 / 원본링크 ][코드] 타 언어처럼 biginteger를 c++에선 지원을 하지않아서... 계산기형식으로만들었다언제나 최적화는 신경1도 안쓰고 푸는데에만 신경쓴다... 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include "stdafx.h"#include #include using namespace::std; #define 지수 2#define 승수 1000int ans = 0;int list[1000] = { 0..

Solution/Project Euler 2018. 5. 25. 20:43