프로젝트 오일러 14~15

프로젝트 오일러 14

양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다.

n → n / 2 (n이 짝수일 때)
n → 3 n + 1 (n이 홀수일 때)

13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다.

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다.
(역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다)

그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는데 가장 긴 과정을 거치는 숫자는 얼마입니까?

참고: 계산 과정 도중에는 숫자가 백만을 넘어가도 괜찮습니다.

-----------------------------------------------------------------------
#include
#define  num 1000000 //num을 백만으로 초기화

long long calc(long long, long long); //사용자 함수

void main()
{
long long count = 0, n = 0, max = 0;
long long i, j;
for (i = 2, j = 2; i < num; j++) //i 가 num일 때까지 반복
{
while (true) //짝수홀수 계산하여 i 가 1 일때까지 무한루프 또한 계산한 것을 count 함.
{
i = calc(i, n);
count++;
if (i == 1)
break;
else
continue;
}
if (j == 2) //처음 count 값을 max로 지정하고
max = count;
else if (count >= max)  //다음 count 가 max 보다 크면 큰 값을 max에 넣는다.
{
max = count;
printf("%lld\n", j );  //max 값이 갱신될 때마다 j값 출력. 마지막에 출력된 값이 답.
}
count = 0; //count 값은 다시 0으로 만들고
i = i + j;  //i는 계속 1로 되므로 j 라는 값을 만들어 수를 키워나감
}
printf("%lld\n", max);   //반복문을 다 돌고 가장 큰 max 값 출력
}

long long calc(long long a, long long b) //짝수일 때와 홀수일 때 계산
{
if (a % 2 == 0) //짝수일 때
b = a / 2;
else if (a % 2 == 1) //홀수일 때
b = 3 * a + 1;

return b; //계산 된 b값을 리턴
}
----------------------------------------------------------------
자료형 long long 때문에 하루종일 걸렸던 문제. long이면 충분 할 줄 알았는데;;
논리 오류인가 싶어서 계속 바꿔도 113383인가 거기서 계속 멈춰서 화가 났다.
누군가 이 글을 볼 지 모르겠지만 113383 이라고 구글링을 치다가 들어와서 long long으로 고쳤으면 좋겠다. 다르게 잘 푸는 사람들도 많겠지만..


프로젝트 오일러 15

아래와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다).

그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까?

-----------------------------------------------------------------------

#include

void main()
{
long long num[21][21];
long long i, j, m, n ,x,y;

for (i = 0; i < 21; i++) //20x20을 모두 1로 만듦
{
for (j = 0; j < 21; j++)
num[i][j] = 1;
}
for (x = 1, y = 0; x < 21; x++, y++) //경우의 수를 모두 더해 마지막 배열을 뽑아낸다.
{
for (m = 1, n = 0; m < 21; m++, n++)
{
num[m][x] = num[m][y] + num[n][x];
}
}

printf("%lld,\n",num[20][20]); //마지막 값 출력
}
--------------------------------------------------------------------
고등학교 때 배웠던 수열문제처럼 풂. 하마터면 14번처럼 데이터 타입 때문에 고생할 뻔 했다. 안되길래 2차배열 값 모두 출력해보니 음수 값이 있어서 long long 으로 바꿔서 하니 답이 나옴.