알고리즘을 좋아하는 나

친절한 문제다.

long long을 사용하라고 문제에 나와있다.

lcm = A * B / gcd

완전제곱수에 1도 포함되는걸 몰라서 계속 틀렸다.

맞왜틀

피보나치 수열을 최대 10000번째 숫자까지 구하는 문제.

딱 봐도 long long 을 넘어간다.

그래서 BigInteger를 사용함(Java)

C++로 구현하다가 계산이 잘 안돼서 그냥 JAVA의 BigInteger를 사용했다.

피보나치 수열을 n으로 나눈 나머지는 주기가 있다.

이 주기를 피사노 주기라고 한다.

나는 이 피사노 주기를 알기 전에 우연히 forloop으로 피보나치 수열을 1000만까지 찍었는데 같은수가 계속 출력돼서 주기가 있다는것을 알았다.

그리고 찾아보니 피사노 주기가 있다는것을 알았다.

2, 5번 문제 동일한 코드다.

동전 문제와 비슷한 풀이다.

tetrahedron에 먼저 사면체에 필요한 폭탄들의 개수를 넣어준다.

그리고 동전 문제처럼 minimumQuantity[tetrahedron[i]] = 1을 해주고,

계산한다.

동전 문제 풀이와 약간 다른점은 동전문제는 나누고나서 뭐 쭉 했다면,

이건 시간초과가 나서  minimumQuantity[i]를 구할 때, minimumQuantity[minimumQuantity[i - tetrahedron[j]] + 1 이런식으로 구했다.

동전문제도 이렇게 변경해서 풀 수 있을거 같다.

coinList[i]에는 i를 만들기위한 최소 동전 개수가 들어간다.

Bottom-Up 방식

Greedy Algorithm은 그 상황에 따라 그 상황이 최적이라고 가정하고, 최적해를 구하는 방법이다.

결론적으로는 해답에 도달한다.

하지만 그 선택들을 수집해서 최종적인 답이 최적이라는 보장이 없다.

Greedy Algorithm은 대부분 두 가지 조건이 만족된다.

1. 탐욕스런 선택 조건(Greedy Choice Proerty): 앞의 선택이 뒤에 영향을 주지 않는다.
2. 최적 부분 구조 조건(Optimal Substructure): 문제에 대한 최적해가 부분문제에 대해서도 최적해다.

문제로 돌아오면,

 K를 만드는 최소의 Ai 개수를 구하는 것이다.

풀이 방법은

오름차순으로 정렬된 동전의 가치를 저장한다.

내림차순으로 동전과 K의 가치를 비교한다. 동전의 가치가 더 크다면 그 동전은 사용하지 않고,

다음 동전으로 넘어간다.

K 가치가 더 큰게 나오면 K -= (K / Ai) * Ai를 해준다.

몇개를 사용하는지 체크해주기 위해 result += (K / Ai)를 해준다.

min ~ max에 i^2 의 배수가 몇개 있는지를 찾는다.

그리고 있으면 count에 더해준다.

이 경우는 n의 m승 이미 계산된거.

이 경우는 i 가 6인경우로 예를 들 수 있다.

i가 6이면 2와 3에서 증가된다.

6의 배수들을 1로 변경해주고,

이 코드에서 6의 배수들이 중복으로 계산됐던걸 빼준다.