28강~31강

28강

접근법 :

• 이번 문제에서는 문제를 잘못 보는 실수를 하였다. 나는 팩토리얼을 통해서 얻은 결과값의 0이 연속적으로 있는 수를 찾는 문제 인줄 알았는데, 알고보니 일의자리부터 0이 몇번 연속적으로 나오느냐 하는 문제였다.

• 아무튼 이 문제에서의 핵심은 팩토리얼을 통해 얻은 값이 lld 형을 넘어서는 거대한 수이기 때문에 팩토리얼 계산을 통해 얻은 결과로 무엇을 하는 것은 불가능하다.

• 그렇기 때문에 다른 방법을 찾아야 한다. 여기서 일의자리부터 0이 몇번 들어가 있는지는 사실 결과값이 10으로 몇번 나누어 지는지에 대해서 묻는 것과 같다.

• 위의 이유로 팩토리얼 계산값의 2와 5가 소인수 분해를 통해서 몇번이나 들어가는지를 확인 하면 된다.

• 그리고 두 수중에서 더 적은 횟수 들어간 소인수가 들어간 횟수가 정답이 된다.

30강

접근법 :

• 이 문제에 경우 어떤 수 전체를 나열해서 그 수에 3이 몇번 들어가는지 묻는 문제이다.

• 이문제를 1초안에 실행되게 하기 위해서는 숫자들 하나하나를 살펴 볼 수는없다.

• 그래서 사용하는 법이 각 자리수에 3을고정하고 나머지 부분이 바뀌는 배타적인 경우의 수를 통해서 답을 구 할 수 있다.

• 먼저 lt, rt, k, cur 이라는 변수를 선언한다. 여기서 cur은 현재 가리키고 있는 자리수에 해당하는 값이다. 그리고 lt는 cur 좌측에 있는 값이다. rt는 cur 우측에 있는 값이고 k는 자릿수를 표현 하는 수이다. 여기서 k=1, lt=77로 초기화를 한다.

• 이제 위에 선언한 변수에 대해서 값을 지정해주어야 한다.
  cur=(n/k)%10, lt=n/(k*10), rt=n%k

• 위의 종합적인 상황에서 이제 결과값을 도출하기 위해서는 세가지로 구간을 나눠야 한다. 먼저 if(cur > 3) 이 경우에는 cur의 값이 3보다 크기 때문에 rt가 0~9까지의 수 모두가 만족한다. 그렇기 때문에 lt의 값이 0~lt 까지 각각 k의 값을 가지게 된다. 그렇기 때문에 값은 (lt+1)*k 가 된다.

• 다음은 else if(cur==3)인 경우이다. 이 경우에는 cur이 3이기 때문에 앞에서는 0~lt-1 까지 각각 k만큼 있고, 그리고 0~rt까지 값이 있다 따라서 lt*k+rt+1 가 된다.

• 마지막으로 cur < 3 인경우는 0~lt-1 까지 각각 k만큼 있는 경우이기 때문에 lt*k가 된다.